POJ 1270 -- Following Orders(Topological Sort,)

POJ 1270 -- Following Orders(Topological Sort,)

Description

Order is an important concept in mathematics and in computer science. For example, Zorn's Lemma states: ``a partially ordered set in which every chain has an upper bound contains a maximal element.'' Order is also important in reasoning about the fix-point semantics of programs.


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

The input consists of a sequence of constraint specifications. A specification consists of two lines: a list of variables on one line followed by a list of contraints on the next line. A constraint is given by a pair of variables, where x y indicates that x < y.


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

For each constraint specification, all orderings consistent with the constraints should be printed. Orderings are printed in lexicographical (alphabetical) order, one per line.


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

http://blog.csdn.net/qq7366020/article/details/8762914
第一行给出字符串(小写字母)，表示出现的字符类型
第二行是约束关系，a1 b1 a2 b2 a3 b3.....ai bi，表示ai必须在bi前面
按照字典序输出所有满足约束条件的序列

解题思路:    题目要求字典序输出，先把给出第一行字符串排序
所有的约束条件变成有向图的边，x z表示顶点x到顶点z的边
序列的情况是否跟有向图有冲突，不冲突则正确，否则舍去
用深搜把所有满足的情况都搜索一边
每次找到入度为0的顶点就开始进入下一层，存入a[len]，并且把与这个顶点相连的点的入度都减1
直到搜索到的层数len等于字符串的长度，就输出a[ ]
也就是在搜索过程中融合拓扑排序的思想，直到不存在入度为0的顶点为止
剪枝:   把字符串转换成数字可以大大提高效率，如y z x 转换为 1 2 0

DFS+拓扑排序
Also check code from http://blog.csdn.net/murmured/article/details/18717137

1. char ch1[MAX],ch2[MAX],ch3[MAX];  
2. int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX];  
3.   
4. bool comp(char a,char b)  
5. {  
6.     return a<b;  
7. }  
8.   
9. void DFS(int len)  
10. {  
11.     int i,j;  
12.     if(len==n)   //层数等于字符串长度则输出  
13.     {  
14.         for(i=0;i<n;i++)  
15.         {  
16.             printf("%c",ch1[a[i]]);  
17.         }  
18.         printf("\n");  
19.         return ;  
20.     }  
21.     for(i=0;i<n;i++)  
22.     {  
23.         if(!visit[i]&&!to[i])  
24.         {  
25.             for(j=0;j<n;j++)   //把与这个顶点相连的点入度减1  
26.             {  
27.                 if(edge[i][j]==1)  
28.                 {  
29.                     to[j]--;  
30.                 }  
31.             }  
32.             visit[i]=1;        //标记此点访问过  
33.             a[len]=i;  
34.             DFS(len+1);  
35.             for(j=0;j<n;j++)   //还原现场: 把减掉的入度加回去  
36.             {  
37.                 if(edge[i][j]==1)  
38.                 {  
39.                     to[j]++;  
40.                 }  
41.             }  
42.             visit[i]=0;        //还原现场  
43.         }  
44.     }  
45.     return ;  
46. }  
47.   
48. int main()  
49. {  
50.     int i,k,pd=0;  
51.     while(gets(ch3))  
52.     {  
53.         if(pd==0)  
54.             pd=1;  
55.         else  
56.             printf("\n");  //测试用例之间输出空行  
57.         gets(ch2);  
58.         memset(zm,-1,sizeof(zm));  
59.         memset(edge,-1,sizeof(edge));  
60.         memset(to,0,sizeof(to));  
61.         memset(visit,0,sizeof(visit));  
62.         for(i=0,n=0;ch3[i]!='\0';i++)   //去除空格  
63.         {  
64.             if(ch3[i]==' ')  
65.                 continue;  
66.             ch1[n++]=ch3[i];  
67.         }  
68.         sort(ch1,ch1+n,comp);           //排序  
69.         for(i=0;i<n;i++)                //字符串1处理,把字母转化成0到n-1的边  
70.         {  
71.             zm[ch1[i]-'a']=i;  
72.         }  
73.         for(i=0,k=0;ch2[i]!='\0';i+=4)  //字符串2处理,构建有向图  
74.         {  
75.             edge[zm[ch2[i]-'a']][zm[ch2[i+2]-'a']]=1;  
76.             to[zm[ch2[i+2]-'a']]++;     //顶点入度+1  
77.         }  
78.         DFS(0);  
79.     //    printf("\n");    这样输出空行poj可以过,UVA会WA  
80.     }  
81.     return 0;  
82. }  

方法2:       利用STL库里面的next_permutation()函数，把所有的字符串全排列都找出
把符合情况的字符串输出，不符合的舍去

1. char ch1[MAX],ch2[MAX],ch3[MAX];  
2. int n,m,zm[MAX],edge[MAX][MAX],to[MAX],visit[MAX],a[MAX];  
3.   
4. bool comp(char a,char b)  
5. {  
6.     return a<b;  
7. }  
8.   
9. int Topsort(char ch[])  
10. {  
11.     int i,j;  
12.     for(i=n-1;i>0;i--)  
13.     {  
14.         for(j=i-1;j>=0;j--)  
15.         {  
16.             if(edge[zm[ch[i]-'a']][zm[ch[j]-'a']]==1)  
17.                 return 0;  
18.         }  
19.     }  
20.     return 1;  
21. }  
22.   
23. int main()  
24. {  
25.     int i,k,pd=0;  
26.     while(gets(ch3))  
27.     {  
28.         if(pd==0)  
29.             pd=1;  
30.         else  
31.             printf("\n");  
32.         gets(ch2);  
33.         memset(zm,-1,sizeof(zm));  
34.         memset(edge,-1,sizeof(edge));  
35.         memset(to,0,sizeof(to));  
36.         memset(visit,0,sizeof(visit));  
37.         for(i=0,n=0;ch3[i]!='\0';i++)   //去空格  
38.         {  
39.             if(ch3[i]==' ')  
40.                 continue;  
41.             ch1[n++]=ch3[i];  
42.         }  
43.         ch1[n]='\0';  
44.         sort(ch1,ch1+n,comp);           //排序  
45.         for(i=0;i<n;i++)                //字符串1处理,把字母转化成0到n-1的边  
46.         {  
47.             zm[ch1[i]-'a']=i;  
48.         }  
49.         for(i=0,k=0;ch2[i]!='\0';i+=4)  //字符串2处理,构建有向图  
50.         {  
51.             edge[zm[ch2[i]-'a']][zm[ch2[i+2]-'a']]=1;  
52.             to[zm[ch2[i+2]-'a']]++;  
53.         }  
54.         if(Topsort(ch1))              //符合限制条件则输出  
55.             printf("%s\n",ch1);  
56.         while(next_permutation(ch1,ch1+n))  
57.         {  
58.             if(Topsort(ch1))          //符合限制条件则输出  
59.                 printf("%s\n",ch1);  
60.         }  
61.     //    printf("\n");  
62.     }  
63.     return 0;  
64. } 

Read full article from 1270 -- Following Orders