UVa872 - Ordering(拓扑排序)

#include <cstdio>#include <cstring>#include <cctype>#include <map>usingnamespacestd;
constintN=220;
constintM=30;
charbuf[N];
boolvis[N];
intt, n;
intg[M][M];
map<char, int>chMap;
map<int, char>intMap;
charans[M];
intp[N], r[N];
voidinput();
voidtoposort(intdep);
boolisCycle();
intfind(intx);
boolUnion(intu, intv);
voidsolve();
intmain()
{
#ifndef ONLINE_JUDGEfreopen("e:\\uva_in.txt", "r", stdin);
#endifintcas;
scanf("%d", &cas);
gets(buf);
while (cas--) {
input();
solve();
if (cas) printf("\n");
    }
return0;
}
voidinput()
{
gets(buf);
gets(buf);
chMap.clear();
intMap.clear();
for (inti=0, len=strlen(buf); i<len; i++) {
if (isalpha(buf[i])) {
intsize=chMap.size();
chMap[buf[i]] =size;
intMap[size] =buf[i];
        }
    }
memset(g, 0x00, sizeof(g));
gets(buf);
for (inti=0, len=strlen(buf); i<len; i+=4) {
chartmp[4];
sscanf(&buf[i], "%s", tmp);
intu=chMap[tmp[0]], v=chMap[tmp[2]];
g[u][v] =1;
    }
n=chMap.size();
}
intfind(intx)
{
introot=x;
while (p[root] !=root) {
root=p[root];
    }
while (p[x] !=root) {
inttmp=x;
x=p[x];
p[tmp] =root;
    }
returnroot;
}
boolUnion(intu, intv)
{
intpu=find(u), pv=find(v);
if (pu==pv) returnfalse;
if (r[pu] <r[pv]) p[pu] =pv;
else {
p[pv] =pu;
if (r[pu] ==r[pv]) r[pu]++;
    }
returntrue;
}
boolisCycle()
{
for (inti=0; i<n; i++) {
p[i] =i;
r[i] =0;
    }
for (inti=0; i<n; i++) {
for (intj=0; j<n; j++) {
if (g[i][j]) {
if (!Union(i, j)) returnfalse;
            }
        }
    }
returntrue;
}
voidtoposort(intdep)
{
if (dep==n) {
for (inti=0; i<n; i++) {
if (i) printf(" ");
printf("%c", ans[i]);
        }
printf("\n");
return;
    }
for (inti=0; i<n; i++) {
if (vis[i]) continue;
intj;
for (j=0; j<n; j++) {
if (j!=i&&!vis[j] &&g[j][i]) break;
        }
if (j>=n) {
vis[i] =true;
ans[dep] =intMap[i];
toposort(dep+1);
vis[i] =false;
        }
    }
}
voidsolve()
{
if (!isCycle()) {
printf("NO\n");
return;
    }
memset(vis, false, sizeof(vis));
toposort(0);
}