| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 5783 | Accepted: 2386 |
Description
Input
Output
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
题目大意：
多组数据输入，每组数据两行，第一行为出现的字母，第二行为字母之间的关系，成对出现，前者小于后者
求满足的拓扑排序，存在多种排序，按字典序升序输出
思路：
在dfs的基础上用拓扑排序
1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 #include <set> 5 using namespace std; 6 7 const int N=30; 8 char s[50],str[150]; 9 int side,x,y,is[N],maps[N][N],vis[N]; 10 set<string> st; 11 12 void init(){ 13 st.clear(); 14 memset(is,0,sizeof is); 15 memset(maps,0,sizeof maps); 16 memset(vis,0,sizeof vis); 17 } 18 19 int check(int x,string res,int cnt){ 20 int flag=1; 21 for(int i=0;i<cnt;i++){ 22 if(maps[x][res[i]-‘a‘]==1){ 23 flag=0; 24 break; 25 } 26 } 27 return flag; 28 } 29 30 void dfs(int cnt,string res){ 31 if(cnt==side){ 32 st.insert(res); 33 } 34 else{ 35 for(int i=0;i<N;i++){ 36 if(is[i]==1&&vis[i]==0&&check(i,res,cnt)){ 37 string cmp=" "; 38 cmp[0]=‘a‘+i; 39 vis[i]=1; 40 dfs(cnt+1,res+cmp); 41 vis[i]=0; 42 } 43 } 44 } 45 } 46 47 int main(){ 48 int ca=0; 49 while(gets(s)){ 50 init(); 51 gets(str); 52 int len=strlen(s); 53 for(int i=0;i<len;i+=2){ 54 is[s[i]-‘a‘]=1; 55 } 56 side=(len+1)/2; 57 len=strlen(str); 58 for(int i=0;i<len;i+=4){ 59 x=str[i]-‘a‘,y=str[i+2]-‘a‘; 60 maps[x][y]=1; 61 } 62 string res=""; 63 dfs(0,res); 64 if(ca)cout<<endl; 65 ca++; 66 for(set<string>::iterator it=st.begin();it!=st.end();it++){ 67 cout<<*it<<endl; 68 } 69 } 70 }
poj1270 Following Orders（拓扑排序+dfs回溯）
原文：https://www.cnblogs.com/ChangeG1824/p/11663767.html