# 題目: 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/