https://pintia.cn/problem-sets/994805342720868352/problems/1071785301894295552
k-coloring
,否则输出No
// Problem: PAT Advanced 1154
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/1071785301894295552
// Tags: Graph Map Set
#include <iostream>
#include <set>
#include <vector>
#include <unordered_map>
using namespace std;
struct Node{int v1, v2;};
int main()
{
int n, m, k;
scanf("%d %d", &n, &m);
vector<Node> edges(m);
for (int i = 0; i < m; i++) // 获取边
scanf("%d %d", &edges[i].v1, &edges[i].v2);
scanf("%d", &k);
while (k--) { // k个着色方案
unordered_map<int, int> vColors;
set<int> colors;
for (int i = 0; i < n ; i++){ // 获取着色方案
scanf("%d", &vColors[i]);
colors.insert(vColors[i]); // 存储颜色
}
bool isYes = true; // 判断着色方案是否符合k着色标准
for (int i = 0; i < m; i++)
if (vColors[edges[i].v1] == vColors[edges[i].v2]){
isYes = false;
break;
}
if (isYes)
printf("%d-coloring\n", colors.size());
else
printf("No\n");
}
return 0;
}
作者:@臭咸鱼
转载请注明出处:https://www.cnblogs.com/chouxianyu/
欢迎讨论和交流!