关于算法-数据结构:PAT甲级1154-Vertex-Coloring

题目粗心：

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