935
技術社區[雲棲]
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;
}
}
最後更新：2017-04-04 07:03:15