| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 4885 | Accepted: 1973 |
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
Source
L← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
foreach node m with an edge e from nto m do
remove edge e from thegraph
ifm has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least onecycle)
else
return L (a topologically sortedorder)
就是找入度为0的点(最好用个stack,循环的话复杂的太高)，加入topo头部
感觉比dfs好，复杂度都是O(V+E)
本题回溯所有方案，复杂度乘上一个V；V很小，不用stack也可以；用个id比较方便吧
字符读入太坑人.........
//
// main.cpp
// poj1270
//
// Created by Candy on 9/11/16.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=,M=;
char s[];
int a[N],num=,n=,id[N];
int ch[N][N],topo[N],ind[N]; void print(){
for(int i=;i<=n;i++) printf("%c",(char)topo[i]+'a'-);
printf("\n");
}
void dfs(int d){ //printf("dfs %d\n",d);
if(d==n+){print();return;}
for(int i=;i<=n;i++)
if(ind[i]==){
ind[i]--; topo[d]=a[i];
for(int j=;j<=ch[i][];j++) ind[ch[i][j]]--;
dfs(d+);
for(int j=;j<=ch[i][];j++) ind[ch[i][j]]++;
ind[i]++;
}
}
int main(int argc, const char * argv[]) {
while(fgets(s,,stdin)){ //printf("p %s\n",s);
n=;
memset(topo,,sizeof(topo));
memset(ch,,sizeof(ch));
memset(ind,,sizeof(ind));
int len=strlen(s); //printf("len %d\n",len);
for(int i=;i<len;i++)
if(s[i]>='a'&&s[i]<='z') a[++n]=s[i]-'a'+;
sort(a+,a++n);
for(int i=;i<=n;i++) id[a[i]]=i; fgets(s,,stdin);
len=strlen(s);
int last=;
for(int i=;i<=len;i++)
if(s[i]>='a'&&s[i]<='z'){
int t=s[i]-'a'+;
t=id[t];
if(last==) last=t;
else{ch[last][++ch[last][]]=t;ind[t]++;last=;}
}
dfs();
printf("\n");
}
return ;
}