acwing::acwing860 命名空间参考

1. 染色法判定二分图

更多...

函数
bool	dfs (vector< unordered_set< int > > &g, int node, vector< int > &color, int c)
int	main (istream &cin, ostream &cout)
	TEST (acwing859, case1)
	TEST (acwing859, case2)

详细描述

1. 染色法判定二分图

函数说明

dfs()

bool acwing::acwing860::dfs	(	vector< unordered_set< int > > &	g,
		int	node,
		vector< int > &	color,
		int	c
	)

在文件 acwing.cpp 第 7481 行定义.

                                                                                     {
            color[node] = c;
            for(const auto sibling: g[node]) {
                if(color[sibling] == 3) {
                    if(!dfs(g, sibling, color, c == 0)) {
                        return false;
                    }
                } else if(color[sibling] == c) {
                    return false;
                }
            }
            return true;
        }

引用了 dfs().

被这些函数引用 dfs() , 以及 main().

main()

int acwing::acwing860::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing.cpp 第 7456 行定义.

                                              {
            int n;
            int m;
            cin >> n >> m;
            vector g(n + 1, unordered_set<int>());
            vector color(n + 1, 3);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                cin >> u >> v;
                g[u].insert(v);
                g[v].insert(u);
            }
            for(int i = 1; i <= n; i++) {
                if(color[i] == 3) {
                    if(!dfs(g, i, color, 0)) {
                        cout << "No";
                        return 0;
                    }
                }
            }
            cout << "Yes";
            return 0;
        }

引用了 dfs().

被这些函数引用 TEST().

TEST() [1/2]

acwing::acwing860::TEST	(	acwing859	,
		case1
	)

在文件 acwing_test.cpp 第 3578 行定义.

                               {
            istringstream in("4 4\n"
                             "1 3\n"
                             "1 4\n"
                             "2 3\n"
                             "2 4");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("Yes", ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing860::TEST	(	acwing859	,
		case2
	)

在文件 acwing_test.cpp 第 3590 行定义.

                               {
            istringstream in("7 7\n"
                             "1 3\n"
                             "1 4\n"
                             "2 3\n"
                             "2 4\n"
                             "5 6\n"
                             "6 7\n"
                             "5 7");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("No", ans);
        }

引用了 main().