L2-3 图着色问题 （25 分) link 图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？
但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。 输入格式：
输入在第一行给出3个整数V（0<V≤500）、E（≥0）和K（0<K≤V），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N（≤20），是待检查的颜色分配方案的个数。随后N行，每行顺次给出V个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。 输出格式：
对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。 输入样例：
6 8 3 2 1 1 3 4 6 2 5 2 4 5 4 5 6 3 6 4 1 2 3 3 1 2 4 5 6 6 4 5 1 2 3 4 5 6 2 3 4 2 3 4输出样例：
Yes Yes No No const int N=1010; int G[N][N]={0}; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; G[a][b]=1; G[b][a]=1; } bool check(){ bool flag=false; for(int j=1;j<=n;j++){ for(int i=1;i<=n;i++){ if(i!=j&&G[j][i]==1&&color[i]==color[j]){ flag=true; break; } } if(flag==true) break; } return flag; } int color[N]={0}; for(int i=0;i<q;i++){ s.clear(); for(int j=1;j<=n;j++){ int tmp; cin>>tmp; color[j]=tmp; s.insert(tmp); } if(s.size()!=c){ cout<<"No\n"; //如果是break的话，就会直接额跳出包裹她的外层循环，后面几个测试行也不测试了 }else{ bool flag=check();//开始打周围一圈，看颜色是否一样 if(flag==true) cout<<"No\n"; else cout<<"Yes\n"; } } //3个整数V（0<V≤500）、E（≥0）和K（0<K≤V）， //分别是无向图的顶点数、边数、以及颜色数。 //图的邻接矩阵 #include <iostream> #include <cstdio> #include <set> using namespace std; const int N=1010; int G[N][N]={0}; int n,m,c; int color[N]={0}; bool check(){ bool flag=false; for(int j=1;j<=n;j++){ for(int i=1;i<=n;i++){ if(i!=j&&G[j][i]==1&&color[i]==color[j]){ flag=true; break; } } if(flag==true) break; } return flag; } int main(){ cin>>n>>m>>c; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; G[a][b]=1; G[b][a]=1; } int q; cin>>q; set<int>s; for(int i=0;i<q;i++){ s.clear(); for(int j=1;j<=n;j++){ int tmp; cin>>tmp; color[j]=tmp; s.insert(tmp); } if(s.size()!=c){ cout<<"No\n"; //如果是break的话，就会直接额跳出包裹她的外层循环，后面几个测试行也不测试了 }else{ bool flag=check();//开始打周围一圈，看颜色是否一样 if(flag==true) cout<<"No\n"; else cout<<"Yes\n"; } } return 0; } #include <iostream> #include <cstdio> #include <vector> #include <set> #include <cstring> using namespace std; vector<int > v[10010]; bool vis[10010]; int color[10010]; bool dfs(int id){//1 vis[id]=true; for(int j=0;j<v[id].size();j++){ int u=v[id][j]; if(color[u]==color[id]){ return false; }else if(vis[u]==false){ dfs(u); } } return true; } int main() { int n,e,k; cin>>n>>e>>k; for(int i=0;i<e;i++){ int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } int num; cin>>num; for(int i=0;i<num;i++){ memset(vis,0,sizeof(vis)); memset(color,-1,sizeof(color)); set<int>s; for(int j=0;j<n;j++){ scanf("%d",&color[j+1]); s.insert(color[j+1]); } if(s.size()!=k){ cout<<"No\n"; continue; } bool flag; for(int i=0;i<n;i++){ //vis[i+1]=true; flag=dfs(i+1);//顶点和颜色都从1到V编号 if(flag==false){ cout<<"No\n"; break; } } if(flag==true)cout<<"Yes\n"; } return 0; }