二分图
一个图是二分图，当且仅当图中不含奇数环（环中边数为奇数）
可以将图划分到两个集合，只存在集合中的边，集合内部没有边
染色法
用dfs来染色，过程中不能出现颜色冲突
要注意什么时候应该递归，否则会出现无限递归的情况
并且这个图不一定联通，需要判断每个连通块是否是二分图
AcWing 860. 染色法判定二分图 原题链接
给定一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图，则输出“Yes”，否则输出“No”。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes
static int n;
static int m;
static int[] colors;
static List<List<Integer>> graph = new ArrayList<>();
private static void add(int a, int b) {
graph.get(a).add(b);
graph.get(b).add(a);
}
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
colors = new int[n + 1];
for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) add(in.nextInt(), in.nextInt());
boolean res = true;
for (int i = 1; i < n + 1; i++) {
if (colors[i] == 0) {
res = staining(i, 1);
if (!res) {
break;
}
}
}
if (res) {
out.println("Yes");
}else {
out.println("No");
}
out.flush();
out.close();
}
private static boolean staining(int idx, int color) {
List<Integer> list = graph.get(idx);
colors[idx] = color;
for (int x : list) {
if (colors[x] == 0) {
if (!staining(x, 3 - color)) {
return false;
}
}else if (colors[x] == color) {
return false;
}
}
return true;
}