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.
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.
For each coloring, print in a line k-coloring if it is a proper k-coloring for some positive k, or No if not.
题意：给出图的顶点数目n和边数目m，再给出边的情况，再给出一个查询数目，每个查询都有顶点数目n个数，第i个颜色是第i个顶点的颜色，求图的边中对应的两个顶点的颜色不同的边的数目。 思路：之前有想过用vector的二维矩阵存储顶点的情况，但是从顶点考虑的话就比较复杂了，于是可以从边开始考虑，先定义一个结构体node，node中存储两个顶点t1,t2,在输入边的时候，就直接对其进行存储。在查询的时候，先用set对不同颜色进行记录，然后用a数组存储所有结点的颜色，只要遍历一下之前存储的边，判断其边所对应的两个顶点的颜色，相同就直接结束了，不相同还是在循环。
#include<iostream> #include<cstdio> #include<stack> #include<queue> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<map> #include<cctype> #include<cstdlib> #include<ctime> #include<unordered_map> using namespace std; //n表示图顶点数目，m表示边数目 int n,m; //边的两个顶点 struct node { int t1,t2; }; int main() { scanf("%d%d",&n,&m); vector<node> v(m); for(int i = 0;i < m;i++) { scanf("%d%d",&v[i].t1,&v[i].t2); } int k;//查询次数 scanf("%d",&k); while(k--) { set<int> s; int a[100010] = {0};//存储每个顶点的颜色 bool flag = true; for(int i = 0;i < n;i++) { scanf("%d",&a[i]); s.insert(a[i]); } for(int i = 0;i < m;i++) { if(a[v[i].t1] == a[v[i].t2]) { flag = false; break; } } if(flag) { printf("%d-coloring\n",s.size()); } else { printf("No\n"); } } return 0; }