本文主要是介绍poj 1270 Following Orders（DFS+拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://poj.org/problem?id=1270
描述：给定几个字母，然后给定几个约束关系，然后打印出满足所有约束关系的字符串
输入：
a b f g
a b b f （满足的约束关系A<B，即a在b前面；b<f,即b在f前面）
v w x y z
v y x v z v w v（满足的约束关系v<y，即v在y前面；x<v,即z在v前面，依次类推....）
输出：
abfgabgfagbfgabfwxzvywzxvyxwzvyxzwvy zwxvyzxwvy
思想：DFS+拓扑排序
代码：
#include<iostream>
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;#define MAX_VERTEX 21int edge[MAX_VERTEX][MAX_VERTEX];//保存边信息
int indegree[MAX_VERTEX];//入度信息
char s1[50];//输入顶点
char s2[50];//输入边
char ans[50];//保存结果char ver[50];//存储边的信息
map<char,int>list;
int numVer;//顶点数void dfs(int k)
{if(k==numVer){printf("%s\n",ans);return;}for(int i=0;i<numVer;i++){if(indegree[i]==0){ans[k] = ver[i];indegree[i]--;for(int j=0;j<numVer;j++){if(edge[i][j])indegree[j]--; }dfs(k+1);indegree[i]++;for(int j=0;j<numVer;j++){if(edge[i][j])indegree[j]++; }}}
}int main()
{int i,j;bool flag=false;while(gets(s1)){int cnt = 0;for(i=0;s1[i]!='\0';i++){if(islower(s1[i])){ver[cnt++] = s1[i];}}sort(ver,ver+cnt);for(i=0;i<cnt;i++)list.insert(make_pair(ver[i],i));numVer = cnt;for(i=0;i<cnt;i++){indegree[i] = 0;ans[i] = '\0';for(j=0;j<cnt;j++)edge[i][j] = 0;}gets(s2);for(i=0;s2[i]!='\0';i++){if(islower(s2[i])){int start = i++;while(!islower(s2[i]))i++;//cout<<s2[start]<<","<<s2[i]<<endl;edge[list[s2[start]]][list[s2[i]]] = 1;indegree[list[s2[i]]]++;}}dfs(0);printf("\n");}system("pause");return 0;
}
这篇关于poj 1270 Following Orders（DFS+拓扑排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
