学步园

模拟水过。

思想：对节点i，找到最小编号并且可以分配的频道j给节点i，告诉i的邻居，你们不能分配频道j。

#include<iostream><br /> #include<cstring><br /> using namespace std;<br /> #define N 30<br /> int mat[N][N],res[N],final[N];<br /> bool s[N][N];<br /> int main()<br /> {<br /> char line[N];<br /> int n,i,j,k,m;<br /> while(scanf("%d",&n),n)<br /> {<br /> memset(mat,0,sizeof(mat));<br /> memset(s,0,sizeof(s));<br /> memset(final,0,sizeof(final));<br /> m=0;<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%s",line);<br /> for(j=2;j<strlen(line);j++)<br /> mat[i][line[j]-'A']=1;<br /> }<br /> for(i=0;i<n;i++)<br /> {<br /> j=0;<br /> while(s[i][j])<br /> j++;<br /> res[i]=j;<br /> for(k=0;k<n;k++)<br /> if(mat[i][k])<br /> s[k][res[i]]=1;<br /> }<br /> for(i=0;i<n;i++)<br /> final[res[i]]++;<br /> for(i=0;i<26;i++)<br /> if(final[i]>0)<br /> m++;<br /> if(m==1)<br /> printf("%d channel needed./n",m);<br /> else<br /> printf("%d channels needed./n",m);<br /> }<br /> return 0;<br /> }