题目链接：http://poj.org/problem?id=1270
这道题其实就是求所有满足条件的topo序，我们考虑到给定的字符是确定的，也就是他们的长度都是一样的，所以为了得到所有的情况，我们可以考虑深度优先搜素和dfs解答树上的回溯。首先，我们从任何一个入度为0的点开始dfs，将这个点的入度-1，防止下一层的搜索中搜到这个点，再更新所有这个点可到达的点的入度，完成这些状态更新之后dfs解答树进入下一层搜索，直到深度值等于串长，输出topo序。回溯的过程中我们需要将之前修改的所有的状态都修改回来。读入的时候要考虑到一次性读入一行，然后进行空格的处理。
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 #include<string.h> 4 #include<map> 5 using namespace std; 6 const int maxn=25; 7 int n,m,t; 8 int vis[maxn],in[maxn],e[maxn][maxn]; 9 char s[100],h[maxn],ans[maxn]; 10 int cnt; 11 void init() 12 { 13 memset(vis,0,sizeof(vis)); 14 memset(in,0,sizeof(vis)); 15 memset(ans,0,sizeof(ans)); 16 memset(e,0,sizeof(e)); 17 } 18 void toposort(int dep) 19 { 20 if(dep==cnt) 21 { 22 printf("%s ",ans); 23 return ; 24 } 25 for(int i=0;i<cnt;i++) 26 { 27 if(in[i]==0&&!vis[i])//只要找到入度为0而且不在topo序中的点就开始搜索，至于回溯和标记则是在递归中进行 28 { 29 vis[i]=1; 30 ans[dep]=h[i]; 31 for(int j=0;j<cnt;j++) 32 if(e[i][j])in[j]--; 33 toposort(dep+1); 34 vis[i]=0; 35 for(int j=0;j<cnt;j++) 36 if(e[i][j])in[j]++;//回溯过程 37 } 38 } 39 } 40 int main() 41 { 42 //freopen("input.txt","r",stdin); 43 //freopen("output.txt","w",stdout); 44 //std::ios::sync_with_stdio(false); 45 while(gets(s))//一次性读取一行字符串在处理 46 { 47 cnt=0; 48 int len=strlen(s); 49 map<char ,int > mp; 50 init(); 51 for(int i=0;i<len;i++) 52 { 53 if(s[i]>='a'&&s[i]<='z')//读掉空格 54 { 55 h[cnt++]=s[i]; 56 } 57 } 58 sort(h,h+cnt);//为了保证最终的topo序是按照字典序输出的，需要给字符集排个序，这样搜索将会变得有序 59 for(int i=0;i<cnt;i++) 60 { 61 mp[h[i]]=i;//将字符集转化成整数集 62 } 63 gets(s); 64 len=strlen(s); 65 int tmp1,tmp2; 66 bool flag=0;//由于是成对出现的，通过对flag的翻转可以确认目前得到的是成对的第一个数还是第二个数 67 for(int i=0;i<len;i++) 68 { 69 if(s[i]>='a'&&s[i]<='z') 70 { 71 if(!flag) 72 { 73 flag=1; 74 tmp1=mp[s[i]];//得到的是成对中的第一个数,并获取编号 75 } 76 else 77 { 78 tmp2=mp[s[i]]; 79 flag=0; 80 e[tmp1][tmp2]=1; 81 in[tmp2]+=1; 82 } 83 } 84 } 85 toposort(0); 86 printf(" ");//注意每个结果之后有一个空行 87 } 88 }