AcWing 860. 染色法判定二分图
原题链接
简单
作者:
goodwill
,
2021-02-05 06:39:50
,
所有人可见
,
阅读 287
Java 版本 DFS, 用Map[HTML_REMOVED]> 来建图,然后遍历每个节点。判断是否能够成功染色
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
map.computeIfAbsent(u, x -> new ArrayList<>()).add(v);
map.computeIfAbsent(v, x -> new ArrayList<>()).add(u);
}
int[] colors = new int[n+1];
boolean flag = true;
for (int i = 1; i <= n; i++) {
if (colors[i] == 0) {
if (!dfs(map, i, 1, colors)) {
flag = false;
break;
}
}
}
if (!flag) System.out.print("No");
else System.out.print("Yes");
}
static boolean dfs(Map<Integer, List<Integer>> map, int x, int color, int[] colors) {
colors[x] = color;
for (int nei : map.getOrDefault(x, new ArrayList<>())) {
if (colors[nei] == 0) {
if (!dfs(map, nei, 3 - color, colors)) return false;
} else if (colors[nei] == color) return false;
}
return true;
}
}