Bandwidth UVA - 140

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <queue>
 4 #include <vector>
 5 #include<string.h>
 6 #include<map>
 7 #include<bits/stdc++.h>
 8 #define LL long long
 9 #define maxn 1005
10 using namespace std;
11 int n,sw;
12 int id[256],letter[10],ans[10],a[10],vis[10];
13 int g[10][10];
14 void dfs(int cur,int bw)
15 {
16     if(cur==n)
17     {
18         if(sw>bw)
19         {memcpy(ans,a,sizeof(int)*n);
20         sw=bw;}
21         return;
22     }
23     for(int i=0;i<n;i++)
24     {
25         if(!vis[i]){
26             int m=0;
27             for(int j=0;j<n;j++)
28             {
29                 if(g[i][j]&&!vis[j])m++;
30             }
31             if(m>=sw)break;
32 
33         int ok=1;
34         a[cur]=i;
35         for(int j=0;j<cur;j++)
36         {
37             if(g[a[j]][i])
38             {
39                 int w=cur-j;
40                 if(w>=sw)
41                 {
42                     ok=0;break;
43                 }
44                 if(w>bw)bw=w;
45             }
46         }
47         if(ok)
48         {
49             vis[i]=1;
50             dfs(cur+1,bw);
51             vis[i]=0;
52         }
53         else break;
54         }
55     }
56 }
57 int main()
58 {
59     char input[1000];
60     while(scanf("%s",input)==1&&input[0]!='#')
61     {
62         n=0;
63         for(char ch='A';ch<='Z';ch++)
64         {
65             if(strchr(input,ch)!=NULL)
66             {
67                 id[ch]=n++;
68                 letter[id[ch]]=ch;
69             }
70         }
71      sw=n;
72      int len=strlen(input),p=0,q=0;
73      memset(g,0,sizeof g);
74      for(;;)
75      {
76          while(p<len&&input[p]!=':')
77             p++;
78             if(p==len)break;
79          while(q<len&&input[q]!=';')
80             q++;
81          for(int i=p+1;i<q;i++)
82          {
83              g[id[input[i]]][id[input[p-1]]]=1;
84              g[id[input[p-1]]][id[input[i]]]=1;
85          }
86          p++,q++;
87      }
88      memset(vis,0,sizeof vis);
89      dfs(0,0);
90      for(int i=0;i<n;i++)
91         printf("%c ",letter[ans[i]]);
92      printf("-> %d\n",sw);
93     }
94     return 0;
95 }