A proper vertex coloring is a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most k colors is called a (proper) k-coloring.

Now you are supposed to tell if a given coloring is a proper k-coloring.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 10
​4
​​ ), being the total numbers of vertices and edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N−1) of the two ends of the edge.

After the graph, a positive integer K (≤ 100) is given, which is the number of colorings you are supposed to check. Then K lines follow, each contains N colors which are represented by non-negative integers in the range of int. The i-th color is the color of the i-th vertex.

Output Specification:
For each coloring, print in a line k-coloring if it is a proper k-coloring for some positive k, or No if not.

Sample Input:
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
Sample Output:
4-coloring
No
6-coloring
No

下面先附一个样例的手绘图，数字是定点编号，交点处为顶点，黑线为边。

这道题其实很简单，但我上去读错了题，我误以为是求每个邻边不同色的顶点的顶点-邻点点集颜色的最大种数，但其实根本没这么麻烦，它只是要判断这个图是否所有相邻顶点两两不同色，如果是，就输出总的颜色种数，如果否，就输出No。

那么只需要存下整个图，扫描每条边判断是否端点异色，同时存储颜色种数即可。我用了邻接表存储。

• 事实证明cin也比scanf慢，如果用cin，最慢用例用时800ms，其他都不改，仅仅把cin换成scanf，最慢用例就变成了250ms

#include<bits/stdc++.h>
#define N 10005
using namespace std;
vector<int> v[N];
int co[N];
int main()  {
    int n,m,k,a,b;
    cin>>n>>m;
    for (int i=0;i<m;i++)   {
        //cin>>a>>b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin>>k;
    for (int i=0;i<k;i++)   {
        for (int j=0;j<n;j++)   scanf("%d",&co[j]); //此处最初j误写了i,找了好久才发现
        int cnt=-1;
        set<int> si;
        for (int p=0;p<n;p++)   {   //对所有邻接表
            si.insert(co[p]);
            for (int y=0;y<(int)v[p].size();y++)    {
                if (co[v[p][y]]==co[p]) {cnt=0;break;}
                si.insert(co[v[p][y]]);
            }
            if (cnt==0) break;
        }
        if (cnt==0) printf("No\n");
        else    printf("%d-coloring\n",(int)si.size());
    }
    return 0;
}

复杂度分析：主要时间消耗在对整个邻接表的遍历上。设顶点n个，边m条，外层双循环总时间复杂度为n，内层set底层是map，map底层是红黑树，查找插入删除都是O(logn),则总复杂度约为O(nlogm)(不一定对，因为这是一个双层循环，并且在不同处有两个插入)。