题意

给定一个无向图，用最少的颜色来涂色，使所有相邻的点颜色都不重复。

思路

数据很小，暴力即可。或者直接贪心(总是选择能选择的id最小的颜色)，下面的代码就是贪心做的。

代码

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 30; const int INF = 1000000000; int cl[maxn]; int n; int cnt = 1; bool eg[maxn][maxn]; bool used[maxn]; char s[maxn]; int main() { //freopen("in.txt","r",stdin); while(scanf("%d",&n) && n) { cnt = 1; memset(cl,0,sizeof(cl)); for(int i = 0 ; i < maxn ; i ++) { fill(eg[i],eg[i]+maxn,0); } for(int i = 0 ; i < n ; i ++) { scanf("%s",s); for(int j = 2 ; j < strlen(s) ; j ++) { eg[s[j]-'A'][i] = eg[i][s[j]-'A'] = true; } } cl[0] = 1; for(int i = 1 ; i < n ; i ++) { //搜第i个点相邻的点 memset(used,false,sizeof(used)); for(int j = 0 ; j < n ; j ++) { if(eg[i][j]) { used[cl[j]] = true; } } //printf("%d\n",used[1]); for(int j = 1 ; j < maxn ; j ++) { if(!used[j]) { cl[i] = j; if(cnt < j) cnt = j; break; } } } //printf("New "); //printf("%d %d %d %d\n",cl[0],cl[1],cl[2],cl[3]); printf("%d channel",cnt); if(cnt > 1) printf("s"); printf(" needed.\n"); } return 0; }