题目粗心:

给出一个图(先给出所有边,后给出每个点的色彩),问是否满足:所有的边的两个点的色彩不雷同,如果存在须要输入不同顶点个数,否则输入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;}