poj 1129

题目：四色问题，就是问你这些点每一个点都要填颜色，最少要几种颜色可以填完，由于题目明确说了是在一个平面，所以最多也就是4种颜色。

思路：DFS，注意一种颜色时那个channel少个s,这个题目的数据不行，所以很多有问题的代码也是可以AC的，但是有些数据是过不了的

5
A:BCDE
B:AC
C:ABD
D:ACE
E:AD
答案应该是3

 1 //这个代码可以过，但是这个数据答案是4，是由于没有回溯
 2 
 3 #include <stdio.h>
 4 #include <string.h>
 5 int n,color,k;
 6 char str[30];
 7 int graph[30][30];
 8 int Ecolor[30];
 9 bool c[6];
10 
11 bool dfs(int x )
12 {
13     memset(c,true,sizeof(c));
14     c[Ecolor[x]] = false;
15     for(int i = 1;i<=n;i++)
16     {
17         if(graph[x][i]&&!Ecolor[i])
18         {
19             for(int j = 1;j<=n;j++)
20             {
21                 if(graph[i][j])
22                     c[Ecolor[j]] = false;
23             }
24             for(k = 1;k<=4;k++)
25             {
26                 if(c[k])
27                 {
28                     if(k>color)
29                         color = k;
30                     Ecolor[i] = k;
31                     if(dfs(i))
32                         break;
33                 }
34             }
35             if(k==5)
36                 return false;
37         }
38     }
39     return true;
40 }
41 
42 int main()
43 {
44     while(scanf("%d",&n),n)
45     {
46         getchar();
47         color = 1;
48         memset(Ecolor,0,sizeof(Ecolor));
49         memset(graph,0,sizeof(graph));
50         for(int i = 1; i <= n ; i++)
51         {
52             scanf("%s",str);
53             for(int j = 2;j<strlen(str);j++)
54             {
55                 graph[i][str[j]-'A'+1] = 1;
56               //  graph[str[j]-'A'+1][i] = 1;
57             }
58         }
59         Ecolor[1] = 1;
60         dfs(1);
61         for(int i = 2;i<=n;i++)
62             if(!Ecolor[i])
63                 dfs(i);
64         if(color==1)
65             printf("1 channel needed.
");
66         else printf("%d channels needed.
",color);
67     }
68     return 0;
69 }

 1 #include <stdio.h>
 2 #include <string.h>
 3 int n,color,k;
 4 char str[30];
 5 int graph[30][30];
 6 int Ecolor[30];
 7 bool flag;
 8 
 9 bool jud(int x,int tot)
10 {
11     for(int i = 1;i<=n;i++)
12         if(graph[x][i]&&Ecolor[i]==tot)
13             return false;
14     return true;
15 }
16 
17 void dfs(int x,int tot)
18 {
19     if(flag)
20         return;
21     if(x>n){
22         flag = true;
23         return;
24     }
25     for(int i = 1;i<=tot;i++){
26         if(jud(x,i))
27         {
28             Ecolor[x] = i;
29             dfs(x+1,tot);
30             Ecolor[x] = 0;
31         }
32     }
33     if(!flag)
34     {
35         color++;
36         dfs(x,tot+1);
37     }
38 }
39 
40 int main()
41 {
42     while(scanf("%d",&n),n)
43     {
44         getchar();
45         color = 1;
46         flag = false;
47         memset(Ecolor,0,sizeof(Ecolor));
48         memset(graph,0,sizeof(graph));
49         for(int i = 1; i <= n ; i++)
50         {
51             scanf("%s",str);
52             for(int j = 2;j<strlen(str);j++)
53             {
54                 graph[i][str[j]-'A'+1] = 1;
55             }
56         }
57         dfs(1,1);
58         if(color==1)
59             printf("1 channel needed.
");
60         else printf("%d channels needed.
",color);
61     }
62     return 0;
63 }