2013年12月2日 星期一

UVA 200 Rare Order

[TOPO SORT]



#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
int Tb[26][26];
bool Exist[26];
int Time[26];
int tt=0;
void dfs(int a)
{
    if(Time[a]) return;
    //printf("DFS:%d\n",a);
    for(int lx=0;lx<26;lx++)
        if((Exist[lx])&&(Tb[a][lx]==-1))
            dfs(lx);
    tt++;
    Time[a]=tt;
    for(int lx=0;lx<26;lx++)
        if((Exist[lx])&&(Tb[lx][a]==1))
            dfs(lx);
}
int main()
{
    memset(Tb,0,sizeof(Tb));
    memset(Exist,false,sizeof(Exist));
    memset(Time,0,sizeof(Time));
    char ss[40];scanf("%s",ss);
    char aa[40];
    for(int lx=0;ss[lx]!='\0';lx++)
        Exist[ss[lx]-'A']=true;
    while(scanf("%s",aa)!=EOF)
    {
        if((aa[0]=='#')&&(aa[1]=='\0')) break;

        for(int lx=0;(ss[lx]!='\0')&&(aa[lx]!='\0');lx++)
        {
            if(aa[lx]!=ss[lx])
            {
                Tb[aa[lx]-'A'][ss[lx]-'A']=1;
                Tb[ss[lx]-'A'][aa[lx]-'A']=-1;
                break;
            }
        }
        strcpy(ss,aa);
        for(int lx=0;ss[lx]!='\0';lx++)
            Exist[ss[lx]-'A']=true;
    }
    int cnt=0;
    for(int lx=0;lx<26;lx++)
        if(Exist[lx]){cnt++;dfs(lx);}
    char str[27];
    for(int lx=0;lx<26;lx++)
    {
        if(Exist[lx])
        {
            //printf("%c:%d\n",lx+'A',Time[lx]);
            str[cnt-Time[lx]]=lx+'A';
        }
    }
    str[cnt]='\0';
    printf("%s\n",str);
    return 0;
}

沒有留言:

張貼留言