PAT甲级1154.

目录

A1154

题目

样例

输入:

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

思路和坑点

  思路:
  记录每个结点的颜色,然后遍历所有的边表,如果发现有两个相邻顶点的颜色一样则不满足要求,否则按照要求输出k-coloring。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct edg{                     //边结点定义
    int a,b;
}Edg;
int n,m;
vector<Edg> v;
void Judge();
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d",&n,&m);
    v.resize(m);
    for(int i=0;i<m;i++)                //读取一个边
        scanf("%d%d",&v[i].a,&v[i].b);
    int k;
    scanf("%d",&k);
    for(int i=0;i<k;i++)                //何查每一组数据
        Judge();
    return 0;    
}
void Judge(){
    map<int,int> color;                 //统计颜色种类        
    bool flag=true;
    vector<int> inc(n);                 //读入序列
    for(int i=0;i<n;i++){
        scanf("%d",&inc[i]);
        color[inc[i]]++;
    }
    for(int i=0;i<m;i++){               //遍历所有的边
        int a=v[i].a,b=v[i].b;
        if(inc[a]==inc[b]){             //如果边的两个顶点颜色相同
            flag=false;                 //则不符合要求
            break;
        }
    }
    if(flag)                            //输出结果
        printf("%d-coloring\n",color.size());
    else
        puts("No");
}