poj 1270 Following Orders 拓扑

这题标准的拓扑排序，用入度为0作为条件dfs比较方便。

唯一要注意的就是输入里会有多余空格……

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int in[26],n;
int edge[26][26],num[26];
char t;
bool input()
{
    memset(in,-1,sizeof(in));
    memset(num,0,sizeof(num));
    n=0;
    bool flag=0;
    while((cin>>t))////输入可能有多个空格
    {
        in[t-'a']=0;n++;
        while(!isalpha(t=getchar()))
            if(t=='\n'){flag=1;break;}
        if(flag)break;
        ungetc(t,stdin);
    }
    if(!n)return 0;
    int now=0,next;
    while(cin>>t)
    {
        now=t-'a';
        cin>>t;
        next=t-'a';
        in[next]++;
        edge[now][num[now]++]=next;
        while(!isalpha(t=getchar()))
            if(t=='\n'){flag=0;break;}
        if(!flag)break;
        ungetc(t,stdin);
    }
    return 1;
}
void change(int now,int flag)
{
    for(int i=0;i<num[now];i++)
        in[edge[now][i]]+=flag;
}
char ans[30]={'\0'};
void dfs(int now)
{
    if(now==n)
    {
        printf("%s\n",ans);
        return;
    }
    for(int i=0;i<26;i++)
    {
        if(in[i]!=0)continue;
        ans[now]=i+'a';
        change(i,-1);//减入度
        in[i]=-1;//防止环
        dfs(now+1);
        in[i]=0;change(i,1);//恢复
    }
    return;
}
int main()
{
   bool flag=0;
   while(input())
   {
       ans[n]='\0';
       if(flag)puts("");
       dfs(0);
       flag=1;
   }
}