给定一个具有n个顶点的图。要给图上每个顶点染色,并且要使相邻的顶点颜色不同。问是否能最多用2种颜色进行染色?题目保证没有重边和自环。
限制条件
1≤n≤1000
例子1
输入 3 3
0 1
1 2
2 0
输出
NO(因为需要3种颜色)
例子2
输入 4 4
0 1
1 2
2 3
3 0
输出
YES(因为0, 2染成一种颜色,1,3染成另一种颜色)
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static int[] color = new int[1001];
public static int V, E;
public static List<Integer>[] list;
public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
V = cin.nextInt();
E = cin.nextInt();
list = (ArrayList<Integer>[]) new ArrayList[V]; // 为了创建邻接链表,每个链表装着该顶点相邻的顶点
for (int i = 0; i < V;++i) { // 这一步容易忘,不然空指针
list[i] = new ArrayList<Integer>();
}
for (int i = 0; i < V; ++i) {
int a = cin.nextInt();
int b = cin.nextInt();
list[a].add(b);
list[b].add(a);
}
cin.close();
solve();
}
// 把顶点染成1或-1
public static boolean dfs(int v, int c) {
color[v] = c; // 把顶点v染成颜色c
int size = list[v].size();
for (int i = 0; i < size; ++i) {
int e = list[v].get(i);
if (color[e] == c) return false; // 如果相邻的顶点同色,则返回false
if (color[e] == 0 && !dfs(e, -c)) return false; // 如果相邻的顶点还没被染色,则染成-c试试
}
// 如果所有顶点都染过色了,则返回true
return true;
}
public static void solve() {
for (int i = 0; i < V; ++i) {
if (color[i] == 0) { // 该顶点还没有被染色
if (!dfs(i, 1)) {
System.out.println("NO");
return;
}
}
}
System.out.println("YES");
}
}
分析:如果是连通图,那么一次dfs就可以访问到所有顶点。如果题目没有说明,那么可能图不是连通的,这样就需要依次检查每个顶点是否访问过。判断是否连通或者是一棵树(没有圈的连通图叫做树),都只需要将dfs进行一些修改就可以了。