POJ1270 Following Orders（拓扑排序+回溯）-白红宇

POJ1270 Following Orders（拓扑排序+回溯）

阅读量：7278 次

发布时间：2019-06-30

本文共 748 字，大约阅读时间需要 2 分钟。

题意：

给出一些字母和这些字母之间的大小关系，要求输出所有满足大小的序列。

要点：

这题其实跟拓扑排序关系不是很大了，主要是输出所有序列比较麻烦，注意题目要求要输出所有的字母，也即是没有在大小关系中出现的字母可以插在任意位置上。我们可以这么想：所有当前入度为0的点可以作为起点，假设一个点的入度为3，说明它的前面起码有3个字母，每次dfs递归深度，寻找下一个入度为0的点，最后再回溯即可。

16128464

Accepted

172K

0MS

1302B

2016-09-27 19:52:09

#include
    
     #include
     
      #include
      #include
       
        using namespace std;const int N = 25;bool graph[N][N];char str[N], ans[N];int indegree[N];int res;map
        
          num;void toposort(int depth){	if (depth == res)//题目中所有字母都会出现	{		printf("%s\n", ans);		return;	}	for (int u = 0; u < res; u++)	{		if (indegree[u] == 0)//入度为0说明可以以当前点为起点		{			indegree[u]--;			ans[depth] = str[u];			for(int v=0;v

转载于:https://www.cnblogs.com/seasonal/p/10343680.html

你可能感兴趣的文章