题目描述
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
染色法
思路:二分图不包含奇数环
相邻的节点的染色不同。若出现相同,则不是二分图
具体代码
public class Main {
private static int N = 100010;
private static int M = N << 1; // 无向图是有向图的二倍
private static int[] h = new int[N];
private static int[] e = new int[M];
private static int[] ne = new int[M];
private static int idx = 0;
private static int[] color = new int[N];
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
Arrays.fill(h, -1);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
add(a, b);
add(b, a);
}
boolean flag = true;
for (int i=1; i<=n; i++) {
if (color[i] == 0) { // 没有染色的点
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) System.out.println("Yes");
else System.out.println("No");
}
private static boolean 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] == 0) {
if (!dfs(j, 3 - c)) return false;
}
// 相邻的节点被染色,判断与相邻的u是否同色
else if (color[j] == c) {
return false;
}
}
return true;
}
// 邻接表
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}