顶点着色 Java题解 （图，模拟）【PAT甲级1154】

输入样例：

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9

输出样例：

4-coloring
No
6-coloring
No

判断图的任意两点是否染色相同，只需要遍历所有的图的边，判断是否有两端点的值相同。

import java.io.*;
import java.util.HashSet;

public class Main {
	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public static int ini() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	
	static class Node{
		int a, b;
		public Node(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}
	
	public static void main(String[] args) throws IOException {
		int n = ini(), m = ini();
		Node []node = new Node[m];
		for(int i = 0; i < m; i++) {
			int a = ini(), b = ini();
			node[i] = new Node(a, b);
		}
		
		int q = ini();
		int []arr = new int[n];
		HashSet set = new HashSet<>();
		while(q-- > 0) {
			for(int i = 0; i < n; i++) {
				arr[i] = ini();
				set.add(arr[i]);
			}
			
			int i = 0;
			for(i = 0; i < m; i++) {  // 遍历的是边数！！
				int a = node[i].a, b = node[i].b;
				if(arr[a] == arr[b]) break;
			}
			if(i == m) System.out.printf("%d-coloringn", set.size());
			else System.out.println("No");
			set.clear();
		}
		
	}
}