| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 5473 | Accepted: 2239 |
Description
This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order.
Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints.
For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y.
Input
All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification.
Input is terminated by end-of-file.
Output
Output for different constraint specifications is separated by a blank line.
Sample Input
a b f g
a b b f
v w x y z
v y x v z v w v
Sample Output
abfg
abgf
agbf
gabf wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy
题目大意：
给你一个有向无环图，请你按字典序输出它所有的toposort结果。
回溯法。
回溯时如果使用了全局变量，要在递归出口处立即还原该全局变量，如ac代码中的vis数组和path数组。
此题输入输出好坑啊。用gets才行，I also not kow why。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
typedef long long ll;
const int maxn=; char str1[],str2[];
int exis[];//26个lowercase字母
int tot;//一共存在多少字母
int cnt;
int to[];
int next[];
int head[];
int in[];//入度
int vis[];
char path[]; void dfs(int x,int m)
{
if(m==tot-)
printf("%s\n",path);
for(int i=head[x];i!=-;i=next[i])
{
int l=to[i];
if(!vis[l])
in[l]--;
}
for(int i=;i<;i++)
{
if(!vis[i]&&exis[i]&&in[i]==)
{
vis[i]=;
path[m+]='a'+i;
dfs(i,m+);
path[m+]='\0';
vis[i]=;
}
}
for(int i=head[x];i!=-;i=next[i])
{
int l=to[i];
if(!vis[l])
in[l]++;
}
} int main()
{
int k=;
while(gets(str1))
{
gets(str2);
if(k>)
printf("\n");
k++; memset(exis,,sizeof(exis));
tot=;
for(int i=;str1[i]!='\0';i++)
{
if(str1[i]>='a'&&str1[i]<='z')
{
exis[str1[i]-'a']=;
tot++;
}
}
cnt=;
memset(head,-,sizeof(head));
memset(in,,sizeof(in));
for(int i=;str2[i]!='\0';i+=)
{
int u=str2[i]-'a',v=str2[i+]-'a';
to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
in[v]++;
} memset(vis,,sizeof(vis));
for(int i=;i<;i++)
path[i]='\0';
for(int i=;i<;i++)
{
if(exis[i]&&in[i]==)
{
vis[i]=;
path[]='a'+i;
dfs(i,);
path[]='\0';
vis[i]=;
}
}
}
return ;
}