# 題目: UVa 10305 - Ordering Tasks

# 題目說明

n 件事及 m 個規則,求符合的順序


INPUT:
第一行有兩個整數 nm ,代表有 n 件事要做,有 m 個規則
接下來有 m 行,每行有兩個整數,代表要先做前者才能做後者


OUTPUT:
符合規則的做事順序

# 解題方法

先建圖,將後者先標為 true
之後跑 dfs ,將走過的點設為 truepushresult

# 參考程式碼

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> graph[101], result;
bool check[101], link[101];
void dfs(int num)
{
	check[num] = true;
	for (auto& i : graph[num]) if (!check[i]) dfs(i);
	result.emplace_back(num);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	int a, b;
	while (cin >> n >> m && (n || m)) {
		fill(graph, graph + 101, vector<int>());
		memset(check, false, sizeof(check));
		memset(link, false, sizeof(link));
		result.clear();
		
		while (m--) {
			cin >> a >> b;
			graph[a].emplace_back(b);
			link[b] = true;
		}
		for (int i = 1; i <= n; ++i) if (!link[i]) dfs(i);
		for (int i = result.size() - 1; i >= 0; --i)
			cout << result[i] << (i != 0 ? " " : "\n");
	}
	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2010305/