题目链接
https://pintia.cn/problem-sets/994805342720868352/problems/1071785301894295552
题解
题目
- k着色:相邻(有共享边)点的颜色不同
- 输入
- N:点的数量,点的编号为[0,N-1],不超过10000
- M:边的数量,不超过10000
- M条边
- K:着色方案的数量,不超过100
- K个着色方案:每行有N个数字,第i个数字就是第i个点的颜色,相同数字代表同色
- 输出
- 对于每个着色方案,如果它是某个k着色,则输出
k-coloring
,否则输出No
- 对于每个着色方案,如果它是某个k着色,则输出
思路
- 把所有边存起来
- 把所有点的颜色存起来,并把颜色放入set中统计颜色个数
- 检查每条边两个点的颜色是否相同
注意点
- cin、cout是会比scanf、printf慢的,如果用cin、cout,第三个测试点可能会超时
代码
// 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/
欢迎讨论和交流!