UVa 10305 Ordering Tasks

想法：
    輸出只要符合是一個topological sort即可，因此可以從起點(沒有被任何點連入的點)用DFS走遍，並同時記錄走遍的點，最後再逆向輸出這些點就是一個topological sort。

	#include <cstdio>
	#include <vector>
	using namespace std;
	void DFS(int n, int visit[], vector<int> toNode[], vector<int> &ans);
	int main()
	{
	int N, M, a, b;
	while (scanf("%d %d", &N, &M) && (N || M)) {
	vector<int> toNode[101];
	vector<int> ans;
	bool connect[101] = {0};
	int visit[101] = {0};
	while (M--) {
	scanf("%d %d", &a, &b);
	toNode[a].push_back(b);
	connect[b] = 1;
	}
	for (int i = 1; i <= N; ++i) {
	if (!connect[i])
	DFS(i ,visit, toNode, ans);
	}
	for (auto iter = ans.end() - 1; iter != ans.begin(); --iter)
	printf("%d ", *iter);
	printf("%d\n", *ans.begin());
	}
	}
	void DFS(int n, int visit[],vector<int> toNode[], vector<int> &ans)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;
	for (int nxt : toNode[n]) {
	if (visit[nxt] != 2)
	DFS(nxt, visit, toNode, ans);
	}
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 10305 Ordering Tasks.cpp hosted with ❤ by GitHub