1154 Vertex Coloring(25 branch)

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 104), 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.

Title Translation:

1154 vertex coloring

"proper vertex coloring" is to mark the vertices of the shape with color, so that two vertices sharing the same edge have different colors. Shading using up to K colors is called k-coloring.

Now you need to indicate whether the given coloring is "k-coloring.".

Input format:

Each input file contains a test case. For each test case, the first line gives two positive integers N and M (no more than 10 ^ 4), respectively representing the total number of vertices and edges. Then there is row M, each of which describes the edge by giving an index (from 0 to N-1) at both ends of the edge.

After describing the edge information, give a positive integer K (< 100), which is the number of shades you need to check. Then it is followed by line K, each of which contains N colors, which are represented by non negative integers in the int range. The ith color represents the color of the ith vertex.

Sample Input:

10 11 / / n vertices, M edges

8 7 / / start vertex of each edge

6 8

4 5

8 4

8 1

1 2

1 4

9 8

9 1

1 0

2 4

4 / / it is necessary to judge the following four cases

The eighth vertex is the third color

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

Topic analysis:

I think it's a difficult point to understand the stem of the problem. I've been reading the translation software for a long time

After reading it, you need to know which data structures are used to store data. Because there are edges and points in this question.

1. The number of sides at the beginning is unknown, which can be stored with variable length array vector

2. For the color of each point, set can be used to store the color (set can be de duplicated and element increment) because "several coloring problems (number of colors)" should be counted

Finally, enumerate the edges to see whether the vertex colors of the edges are consistent. If they are consistent, it is not a n-coloring problem.

Code display:

#include<iostream> #include<cstdio> #include<vector> #include<set> using namespace std; struct node { int p1,p2; }; int main() { int m,n,k; cin>>m>>n;//m points, n edges vector<node> bian(n);//Must be initialized and must be parenthesized for(int i=0;i<n;i++) { scanf("%d %d",&bian[i].p1,&bian[i].p2);//scanf read in time is shorter than cin read in time } cin>>k; while(k>0) { int dian[10000]={0};//Array initialization is very important. The color of the storage point is not more than 10000 set<int> s; bool flag=true; for(int j=0;j<m;j++) { scanf("%d",&dian[j]); s.insert(dian[j]); } for(int q=0;q<n;q++)//Enumerate n edges { if(dian[bian[q].p1]==dian[bian[q].p2]) { flag=false; break; } } if(flag==false) { cout<<"No"<<endl; } else { cout<<s.size()<<"-coloring"<<endl; } k--; } }

summary

I'm really tired to write this question, and my mind is exploding.

There are several problems

1. The size of the color array of storage points must be no larger than 10000 according to the requirements of the title, or segment error will occur.

2.vector is a variable length array, which needs to be read in the way of array and needs to be initialized. Initialization must be in parentheses. Is not a square bracket. Otherwise, there is an error.

3. The reading time of scanf is shorter than that of cin

Come on, keep going.