# 題目: UVa 10305 - Ordering Tasks

# 題目說明

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

---

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

---

OUTPUT:
符合規則的做事順序

# 解題方法

先建圖，將後者先標為true
之後跑dfs，將走過的點設為true並push到result

# 參考程式碼

#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/