题目粗心:
给出一个图(先给出所有边,后给出每个点的色彩),问是否满足:所有的边的两个点的色彩不雷同,如果存在须要输入不同顶点个数,否则输入No。
算法思路:
咱们应用set diff_colors
保留每一次输出的每一个顶点,其大小就是不同顶点的个数,而后遍历每一条边,如果呈现一条边的2个顶点色彩雷同的状况,阐明不存在k-coloring
,输入No,否则输入diff_colors
汇合的大小。
提交后果:
AC代码:
#include<cstdio>#include<unordered_set>using namespace std;struct Edge{ int a,b;}edges[10005];int N,M;// 顶点和边的数目unordered_set<int> diff_colors;int colors[10005];// 记录每一个节点的色彩int main(){ scanf("%d %d",&N,&M); int a,b; for (int i = 0; i < M; ++i) { scanf("%d %d",&a,&b); edges[i].a = a; edges[i].b = b; } int K; scanf("%d",&K); for (int j = 0; j < K; ++j) { int color; bool proper = true; diff_colors.clear();// 每一次都得清空 for (int i = 0; i < N; ++i) { scanf("%d",&color); colors[i] = color; diff_colors.insert(color); } // 遍历每一条边 for (int k = 0; k < M; ++k) { int u = edges[k].a; int v = edges[k].b; if(colors[u]==colors[v]){ // 一条边的2个顶点呈现色彩雷同的状况 proper = false; break; } } if(proper){ printf("%lu-coloring\n",diff_colors.size()); } else { printf("No\n"); } } return 0;}