hdu Channel Allocation 深搜dfs

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int color[30],map[30][30];
 6 int flag,n;
 7 int check(int a,int b)
 8 {
 9     int i;
10     for(i=0;i<n;i++)
11     {
12         if(map[i][a]&&color[i]==b)
13         return 0;
14     }
15     return 1;
16 }
17 void dfs(int pos,int num)
18 {
19     int i;
20     if(flag==1) return ;
21     if(pos==n)
22     {
23         printf("%d channels needed.\n",num-1);
24         flag=1;
25         return ;
26     }
27     if(flag==1) return ;
28     for(i=1;i<num;i++)
29     {
30         if(check(pos,i))
31         {
32             color[pos]=i;
33             dfs(pos+1,num);
34         }
35     }
36     color[pos]=num;
37     dfs(pos+1,num+1);
38 }
39 int main()
40 {
41     int i,j;
42     char str[30];
43     while(scanf("%d",&n),n)
44     {
45         flag=0;
46         for(i=0;i<n;i++)
47         {
48             for(j=0;j<n;j++)
49             map[i][j]=0;
50         }
51         for(j=0;j<n;j++)
52         {
53             scanf("%s",str);
54             int len=strlen(str);
55             int a=str[0]-‘A‘;
56             for(i=2;i<len;i++)
57             {
58                 int b=str[i]-‘A‘;
59                 map[a][b]=map[b][a]=1;
60             }
61         }
62         dfs(0,1);
63     }
64     return 0;
65 }