A propervertexcoloring isalabelingofthegraph'sverticeswithcolorssuchthatnotwoverticessharingthesameedgehavethesamecolor.Acoloringusingatmost k colorsiscalleda(proper) k-coloring.
Nowyouaresupposedtotellifagivencoloringisaproper k-coloring.
InputSpecification:
Eachinputfilecontainsonetestcase.Foreachcase,thefirstlinegivestwopositiveintegers N and M (bothnomorethan 104),beingthetotalnumbersofverticesandedges,respectively.Then M linesfollow,eachdescribesanedgebygivingtheindices(from0to N−1)ofthetwoendsoftheedge.
Afterthegraph,apositiveinteger K (≤ 100)isgiven,whichisthenumberofcoloringsyouaresupposedtocheck.Then K linesfollow,eachcontains N colorswhicharerepresentedbynon-negativeintegersintherangeof int.The i-thcoloristhecolorofthe i-thvertex.
OutputSpecification:
Foreachcoloring,printinaline k-coloring ifitisaproper k-coloringforsomepositive k,or No ifnot.
SampleInput:1011876845848112149891102440101410130010141010081014105301234567889SampleOutput:4-coloringNo6-coloringNo数据结构：vector<vector<int>>;(因为没有权值) 存边
vector<int>存颜色
#include<iostream>#include<string>#include<sstream>#include<vector>#include<algorithm>#include<cmath>#include<map>usingnamespacestd;//11:50图论intmain(){freopen("C:\\Users\\chenzhuo\\Desktop\\in.txt","r",stdin);intn,m;cin>>n>>m;vector<vector<int>>tmp(n);for(inti=0;i<m;i++){inta,b;cin>>a>>b;tmp[a].push_back(b);}intk;cin>>k;for(inti=0;i<k;i++){vector<int>col(n);intflag=1;intnum=0;//颜色数量map<int,int>mp;for(intj=0;j<n;j++){cin>>col[j];if(mp[col[j]]!=1){num++;mp[col[j]]=1;}}for(intj=0;j<n;j++)//遍历n个顶点{for(autod:tmp[j])//对于每个顶点{if(col[j]==col[d]){cout<<"No"<<endl;flag=0;break;}}if(flag==0){break;}}if(flag==1)//输出{cout<<num<<"-coloring"<<endl;}}}
