PAT_A1154
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");
}