代码
import java.util.*;
import java.io.*;
public class Main {
static int N = 100010, n, idx;
/**
* 邻接表存点边关系
*/
static int[] h = new int[N];
static int[] e = new int[2 * N];
static int[] ne = new int[2 * N];
/**
* 节点染色数组,0 表示未染色,1 表示集合A染色,2 表示集合B染色
*/
static int[] co = new int[N];
/**
* 点边关系存入邻接表
*/
static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
/**
* DFS 染色,返回值为当前染色过程是否有冲突。有 返回 true,没有返回 false
*/
static boolean dfs(int u, int c) {
// 给当前点染色
co[u] = c;
// 遍历当前点的所有连接点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
// 如果连接点未染色
if (co[j] == 0) {
// 给连接点 DFS 染色,色彩要与当前点不同。如果染色过程有冲突,则返回 true
if (dfs(j, 3 - c)) return true;
}
// 如果连接点已染色,并且与当前点色彩一致。则表示染色有冲突,返回 true
else if (co[j] == c) return true;
}
// 染色无误,返回 false
return false;
}
/**
* 染色检查
*/
static boolean check() {
boolean f = true;
// 遍历所有点
for (int i = 1; i <= n; i ++) {
// 如果当前点没有染色
if (co[i] == 0) {
// 进行 DFS 染色,如果染色过程有冲突,则表示不是二分图,返回 false
if (dfs(i, 1)) {
f = false;
break;
}
}
}
// 返回二分图判断
return f;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
n = sc.nextInt();
int m = sc.nextInt();
Arrays.fill(h, -1);
while (m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
add(b, a);
}
System.out.println(check() ? "Yes" : "No");
sc.close();
}
}