题目描述

已知染色方案，判断该染色方案是否合理
如果合理，通过set统计染色使用的颜色数

算法1

C++ 代码

#include<iostream>
#include<set>
using namespace std;
const int N=1e4+10;
const int M=1e4+10;
int n,m;
int color[N];
struct edge{
    int a,b;
}e[M];

int main(){
    cin>>n>>m;

    for(int i=0;i<m;i++){
        cin>>e[i].a>>e[i].b;
    }

    int k;
    cin>>k;

    for(int i=0;i<k;i++){
        set<int> s;
        for(int i=0;i<n;i++){
            cin>>color[i];//一种染色方案
        }
        //判断该种染色方案是否可以满足所有边的端点染色不同
        bool flag=true;
        for(int i=0;i<m;i++){
            if(color[e[i].a]==color[e[i].b]){
                flag=false;
                break;
            }
        }
        if(flag){
            //该染色方案合理
            for(int i=0;i<n;i++){
                s.insert(color[i]);
            }
            cout<<s.size()<<"-coloring"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }

    return 0;
}