【1154】Vertex Coloring (25 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<set>
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      先存边，再存点颜色进a数组 同时 进se集合(方便统计颜色种类数)
     
    
   

    

     

    
    

     

      遍历每条边判断边两端(点) a[v[i].t1] ==a[v[i].t2],有相同则跳出
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct node { int t1,t2;};//大括号内不要漏了分号
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	int n,m,k;
     
    
   

    

     

    
    

     

      	cin >> n >>m; //n个点 m条边
     
    
   

    

     

    
    

     
	vector<node> v(m); //用m个node空间存放m条边，注意不是[]
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++){ //遍历m条边保存起始点
     
    
   

    

     

    
    

     
		scanf("%d %d",&v[i].t1,&v[i].t2);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	cin >> k; //k次测试
     
    
   

    

     

    
    

     
	while(k--){
     
    
   

    

     

    
    

     
		int a[10009]={0};//存放每个点的颜色
     
    
   

    

     

    
    

     
		bool flag=true;
     
    
   

    

     

    
    

     

      		set<int> se; //用set方便后面输出颜色种类数
     
    
   

    

     

    
    

     
		for(int i=0;i<n;i++){ //n个点的颜色初始化
     
    
   

    

     

    
    

     
			scanf("%d",&a[i]);
     
    
   

    

     

    
    

     

      			se.insert(a[i]);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		for(int i=0;i<m;i++){//遍历每一条边,与se无关！！
     
    
   

    

     

    
    

     
			if(a[v[i].t1] ==a[v[i].t2]){ 
     
    
   

    

     

    
    

     

      				flag=false;//如果每条边的两端(点)颜色相同则false
     
    
   

    

     

    
    

     
				break;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if(flag){
     
    
   

    

     

    
    

     
			printf("%d-coloring\n",se.size());
     
    
   

    

     

    
    

     

      		}else{
     
    
   

    

     

    
    

     
			printf("No\n");
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	system("pause"); 
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99640179