uva 10305 Ordering Tasks 拓扑排序 逆DFS法和一般法

本文主要是介绍uva 10305 Ordering Tasks 拓扑排序 逆DFS法和一般法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9

只需输出拓扑排序的一种情况即可AC。

代码如下：

一般法：

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
vector<int>topsort[100+5];
int InDegree[100 + 5];
int sort[100 + 5];
int main()
{int n, m,k;	while (cin >> n >> m && (n || m)){int u, v;memset(InDegree, 0, sizeof(InDegree));for (int i = 0; i <= n;i++)if (!topsort[i].empty())topsort[i].clear();k = 0;while (m--){cin >> u >> v;topsort[u].push_back(v);InDegree[v]++;			//记录入度}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (InDegree[j] == 0){sort[k++] = j;InDegree[j]--;for (int h = 0; h < topsort[j].size(); h++)		//对应的入度的点-1InDegree[topsort[j][h]]--;break;}}}//cout <<endl <<k << " " << n << endl;if (k == n){for (int i = 0; i < k-1; i++)cout << sort[i] << " ";cout << sort[k - 1] << endl;}}return 0;
}

逆DFS法（参考刘汝佳书）：

原理：不断的找出度为0的点，排好序后，逆序输出便是拓扑排序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int TopoSort[100 + 2][100 + 2];
bool FlagSort[100 + 2];		//标记该点是否被遍历过。1遍历过，0没有遍历过，-1正在遍历
int sort[100 + 2];
int n, m ,t;
bool DFS(int i)
{FlagSort[i] = -1;for (int j = 1; j <= n; j++){if (TopoSort[i][j]){if (FlagSort[j] < 0) return false;if (!FlagSort[j] && !DFS(j)) return false;}}FlagSort[i] = 1;		//出度为0的点sort[--t] = i;return true;
}
bool toposort()
{t = n;memset(FlagSort, 0, sizeof(FlagSort));for (int i = 1; i <= n; i++){if (!FlagSort[i]){if (!DFS(i)) return false;}}return true;
}
int main()
{while (cin >> n >> m && (n || m)){int u,v;memset(TopoSort, 0, sizeof(TopoSort));while (m--){cin >> u >> v;TopoSort[u][v] = 1;}if (toposort()){for (int i = 0; i < n-1; i++)cout << sort[i] << " ";cout << sort[n - 1] << endl;}}return 0;
}

这篇关于uva 10305 Ordering Tasks 拓扑排序 逆DFS法和一般法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---