簡單回溯，枚舉所有情況，在linux下用Emacs編譯有點不習慣，編碼調(diào)試都花了不少時間， 希望以后熟練之后會好很好多。
#include <stdio.h>
#include <string.h>
#define N 30
int g[N][N], num[10], ans[10], top, bandwidth, mostBand;
bool mk[N], vst[N];
inline int ABS(int x) {
return x > 0 ? x : -x;
}
void dfs(int u, const int &n) {
num[top++] = u;
if(top == n) {
bandwidth = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(g[num[i]][num[j]]) {
if((j - i) > bandwidth){
bandwidth = (j - i);
}
}
}
}
if(bandwidth < mostBand) {
for(int k = 0; k < n; k++) {
ans[k] = num[k];
}
mostBand = bandwidth;
}
}
else {
for(int i = 0; i < 26; i++) {
if(mk[i] && !vst[i]) {
vst[i] = 1;
dfs(i, n);
vst[i] = 0;
}
}
}
top--;
}
int main()
{
//freopen("in", "r", stdin);
char data[1005];
while(gets(data), strcmp(data, "#")) {
memset(g, 0, sizeof(g));
memset(mk, 0, sizeof(mk));
memset(vst, 0, sizeof(vst));
mostBand = 100;
char *p;
int l, a, b, n = 0;
p = strtok(data, ";");
while(p) {
l = strlen(p);
mk[a = p[0] - 'A'] = 1;
for(int i = 2; i < l; i++) {
b = p[i] - 'A';
mk[b] = 1;
g[a][b] = g[b][a] = 1;
}
p = strtok(NULL, ";");
}
for(int i = 0; i < 26; i++) {
if(mk[i]) n++;
}
/* printf("n = %d\n", n);
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
if(g[i][j])printf("%c->%c\n", 'A' + i, 'A' + j);
}
printf("\n");
}*/
for(int i = 0; i < 26; i++) {
top = 0;
if(mk[i] && !vst[i]) {
vst[i] = 1;
dfs(i, n);
vst[i] = 0;
}
}
for(int i = 0; i < n; i++) {
printf("%c ", ans[i] + 'A');
}
printf("-> %d\n", mostBand);
}
}