UVa140 Bandwidth

#include <stdio.h>#include <string.h>#include <ctype.h>#include <stdlib.h>#define MAXN 30#define BUFLEN 80#define STRLEN 30intgraph[MAXN][MAXN];
inthasChar[STRLEN];
intChar[STRLEN];
intlen;
intvis[STRLEN];
intmax;
intresult[STRLEN];
intans[STRLEN];
intcmp_char(constvoid*a, constvoid*b);
voiddfs(intcur);
intmain()
{
inti;
charbuf[BUFLEN];
intstart, end;
#ifndef ONLINE_JUDGEfreopen("d:\\uva_in.txt", "r", stdin);
#endifwhile (scanf("%s", buf) &&buf[0] !='#') {
memset(hasChar, -1, sizeof(hasChar));
memset(graph, 0, sizeof(graph));
memset(vis, 0, sizeof(vis));
max=100;
i=0;
len=0;
while (i<strlen(buf)) {
start=buf[i] -'A';
if (hasChar[start] ==-1) {
hasChar[start] =1;
Char[len++] =start;
            }
i+=2;
while (isalpha(buf[i])) {
end=buf[i] -'A';
if (hasChar[end] ==-1) {
hasChar[end] =1;
Char[len++] =end;
                }
graph[start][end] =graph[end][start] =1;
i++;
            }
i++;
        }
qsort(Char, len, sizeof(int), cmp_char);
dfs(0);
for (i=0; i<len; i++) {
printf("%c ", ans[i] +'A');
        }
printf("-> %d\n", max);
    }
return0;
}
intcmp_char(constvoid*a, constvoid*b)
{
constint*tmp_a= (constint*)a;
constint*tmp_b= (constint*)b;
return*tmp_a-*tmp_b;
}
voiddfs(intcur)
{
inti, j;
inttemp;
if (cur==len) {
temp=0;
for (i=0; i<cur-1; i++) {
for (j=i+1; j<cur; j++) {
if (graph[result[i]][result[j]] && (j-i) >temp)
temp=j-i;
            }
        }
if (temp<max) {
max=temp;
memcpy(ans, result, sizeof(result));
        }
    } else {
for (i=0; i<len; i++) {
if (!vis[i]) {
vis[i] =1;
result[cur] =Char[i];
dfs(cur+1);
vis[i] =0;
            }
        }
    }
}