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/

欢迎讨论和交流!


上一篇:POJ-1308 Is It A Tree?(直接写的题)


下一篇:LeetCode 1489. 找到最小生成树里的关键边和伪关键边