AcWing 860. 染色法如何判定二分图？

本文共计508个文字，预计阅读时间需要3分钟。

题目：给定一个无向图，判断该图是否为二分图。给定一个无向图，包含n个点和m条边，请输出该图是否为二分图。

输入格式：第一行包含两个整数n和m。接下来m行，每行包含两个整数u和v，表示点u和点v之间有一条边。

输出格式：输出一个字符串，YES表示该图是二分图，NO表示该图不是二分图。

题目

给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式 第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示点 $u$ 和点 $v$ 之间存在一条边。

输出格式 如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围 $1≤n,m≤10^5$ 输入样例：

4 4 1 3 1 4 2 3 2 4

输出样例：

Yes

思路

二分图：可以把所有点分成两个集合，边不在集合中 二分图不含奇数环

算法思路：

for i in 1~n if !color[i] dfs(i, 1)

代码

#include <cstring> #include <iostream> using namespace std; const int N = 100010, M = 200010; int n, m; int h[N], e[M], ne[M], idx; int color[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!color[j]) { if (!dfs(j, 3 - c)) return false; } else if (color[j] == c) return false; } return true; } int main() { cin >> n >> m; memset(h, -1, sizeof h); while (m -- ) { int a, b; cin >> a >> b; add(a, b); add(b, a); } bool flag = true; for (int i = 1; i <= n; i ++ ) { if (!color[i]) { if (!dfs(i, 1)) { flag = false; break; } } } if (flag) puts("Yes"); else puts("No"); return 0; }