AcWing 860. 染色法判定二分图
原题链接
简单
作者:
gongjin
,
2023-01-03 18:21:51
,
所有人可见
,
阅读 99
热色法判定二分图(dfs) JAVA实现
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
class Main {
static ListNode[] head;
static int[] color;
static int n;
static int m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
head = new ListNode[n + 1];
color = new int[n + 1];
for (int i = 1; i <= n; i++) {
head[i] = new ListNode(i);
}
for (int i = 0; i < m; i++) {
int n1 = scanner.nextInt();
int n2 = scanner.nextInt();
ListNode node = new ListNode(n2);
node.next = head[n1].next;
head[n1].next = node;
ListNode node1 = new ListNode(n1);
node1.next = head[n2].next;
head[n2].next = node1;
}
for (int i = 1; i <= n; i++) {
if (color[i] == 0 && !dfs(i, 1)) {
System.out.println("No");
return;
}
}
System.out.println("Yes");
}
public static boolean dfs(int u, int c) {
color[u] = c;
ListNode node = head[u].next;
while (node != null) {
if (color[node.val] == 0 && !dfs(node.val, 3 - c)) {
return false;
} else if (color[node.val] == c) {
return false;
}
node = node.next;
}
return true;
}
}