PAT_A1154#Vertex Coloring

Source:

PAT A 1154 Vertex Coloring (25 分)

Description:

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 1), 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

Keys:

图的存储和遍历
set（C++ STL）
散列（Hash）

Attenrion:

矩阵存储图，规模小于10^3
对于多组测试用例的输入，要注意统计值和哈希函数的初始化（出题老师太坏了，测试用例即使不初始化也是对的-,-）

Code:

 /*

 Data: 2019-08-02 21:08:29

 Problem: PAT_A1154#Vertex Coloring

 AC: 17:39

 题目大意：

 判断图中相连的顶点是否共色

 */

 #include<cstdio>

 #include<set>

 using namespace std;

 const int M=1e4+;

 struct node

 {

     int u,v;

 }grap[M];

 int color[M];

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int n,m,k;

     scanf("%d%d", &m,&n);

     for(int i=; i<n; i++)

         scanf("%d%d", &grap[i].u,&grap[i].v);

     scanf("%d", &k);

     while(k--)

     {

         set<int> mp;

         for(int i=; i<m; i++)

         {

             scanf("%d", &color[i]);

             mp.insert(color[i]);

         }

         for(int i=; i<n; i++)

         {

             if(color[grap[i].u] == color[grap[i].v])

             {

                 mp.clear();

                 break;

             }

         }

         if(mp.size())

             printf("%d-coloring\n", mp.size());

         else

             printf("No\n");

     }

     return ;

 }

巴特西

PAT_A1154#Vertex Coloring

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

Attenrion:

Code:

最新文章

热门文章