PAT甲级1154Vertex Coloring

题目链接

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

思路

1. 把所有边存起来
2. 把所有点的颜色存起来，并把颜色放入set中统计颜色个数
3. 检查每条边两个点的颜色是否相同

注意点

• 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/

欢迎讨论和交流!

---