【1154】Vertex Coloring (25 分)
【摘要】
#include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm> #include<map>#inclu...
-
#include<iostream>
-
#include<stdio.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<map>
-
#include<vector>
-
#include<queue>
-
#include<set>
-
using namespace std;
-
先存边,再存点颜色进a数组 同时 进se集合(方便统计颜色种类数)
-
遍历每条边判断边两端(点) a[v[i].t1] ==a[v[i].t2],有相同则跳出
-
-
struct node { int t1,t2;};//大括号内不要漏了分号
-
-
int main(){
-
int n,m,k;
-
cin >> n >>m; //n个点 m条边
-
vector<node> v(m); //用m个node空间存放m条边,注意不是[]
-
for(int i=0;i<m;i++){ //遍历m条边保存起始点
-
scanf("%d %d",&v[i].t1,&v[i].t2);
-
}
-
cin >> k; //k次测试
-
while(k--){
-
int a[10009]={0};//存放每个点的颜色
-
bool flag=true;
-
set<int> se; //用set方便后面输出颜色种类数
-
for(int i=0;i<n;i++){ //n个点的颜色初始化
-
scanf("%d",&a[i]);
-
se.insert(a[i]);
-
}
-
for(int i=0;i<m;i++){//遍历每一条边,与se无关!!
-
if(a[v[i].t1] ==a[v[i].t2]){
-
flag=false;//如果每条边的两端(点)颜色相同则false
-
break;
-
}
-
}
-
if(flag){
-
printf("%d-coloring\n",se.size());
-
}else{
-
printf("No\n");
-
}
-
}
-
system("pause");
-
return 0;
-
}
文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。
原文链接:andyguo.blog.csdn.net/article/details/99640179
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)