poj1270 拓扑序（DFS）

题意：给出将会出现的多个字母，并紧接着给出一部分字母的大小关系，要求按照字典序从小到大输出所有符合上述关系的排列。

拓扑序，由于需要输出所有排列，所以需要使用 dfs ，只要点从小到大遍历就可以实现字典序排列了。

 #include<stdio.h>

 #include<string.h>

 int ma[][],id[],vis[],v[],n;

 char s[],ans[];

 char read(){

     char c=getchar();

     while((c>'z'||c<'a')&&(c!='\n'))c=getchar();

     return c;

 }

 void dfs(int ss,int t){

     ans[t]=ss+'a';

     v[ss]=;

     if(t==n){

         for(int i=;i<=n;++i)printf("%c",ans[i]);

         printf("\n");

         v[ss]=;

         return;

     }

     int que[],cnt=;

     for(int i=;i<;++i){

         if(ma[ss][i])id[i]--;

         if(vis[i]&&!id[i]&&!v[i])que[++cnt]=i;

     }

     for(int i=;i<=cnt;++i)dfs(que[i],t+);

     for(int i=;i<;++i)if(ma[ss][i])id[i]++;

     v[ss]=;

 }

 int main(){

     int ccnt=;

     while(scanf("%s",s)!=EOF){

         if(ccnt++)printf("\n");

         memset(ma,,sizeof(ma));

         memset(id,,sizeof(id));

         memset(vis,,sizeof(vis));

         memset(v,,sizeof(v));

         n=;

         vis[s[]-'a']=;

         n++;

         char c1,c2;

         while(c1=getchar()){

             if(c1=='\n')break;

             if(c1>'z'||c1<'a')continue;

             int cc=c1-'a';

             if(!vis[cc]){

                 vis[cc]=;

                 n++;

             }

         }

         bool f=;

         while(f){

             c1=read();

             if(c1=='\n')break;

             c2=read();

             int cc1=c1-'a',cc2=c2-'a';

             if(!ma[cc1][cc2]){

                 ma[cc1][cc2]=;

                 id[cc2]++;

             }

         }

         for(int i=;i<;++i)if(vis[i]&&!id[i])dfs(i,);

     }

     return ;

 }