alan23273850 的刷題筆記
c131: 00615 - Is It A Tree?
出處：https://zerojudge.tw/ShowProblem?problemid=c131
提交：https://zerojudge.tw/Submissions?problemid=c131&account=allllllan123456
問題：給定一些構成目標圖的有向邊，目標圖的頂點必須存在於至少一條有向邊才會存在，換言之我們不用考慮孤立點的問題，請問這張目標圖是否符合一棵樹的定義？一棵樹可以沒有任何頂點與邊，否則：
- 只能有一個頂點，我們稱之為根頂點 (root)，完全沒有邊指向他。
- 只要不是 root，都只能剛好有一條邊指向它。
- 從 root 到任何一個頂點都只能有一條唯一的路徑。
解法：網路上很多解法都有提到要檢查有沒有環，其實不然。對於一張非空的圖，我們可以在輸入有向邊的時候就記錄每個頂點的上/下游頂點，如果已經有上游頂點的人又再度被指派另一個上游頂點，則違反條件 2. 直接判斷失敗，所以在有向邊輸入完畢的時候每人至多只會有一個上游頂點。現在重新檢查每個頂點的上游，確認無上游頂點是否剛好只有一個，如果不是則違反條件 1. 直接判斷失敗，否則指派該唯一頂點為 root，到這裡就確定至少滿足條件 1. 2. 了。注意到如果要違反條件 3.，也就是有至少兩條路徑可以從 root 到某特定頂點，那至少要有一個頂點有兩個以上的上游頂點才能達到，這已經違反條件 2.，因此從 root 到任何一個頂點至多就只會有一條路徑可以到達；但還有一種狀況也違反條件 3. 就是有頂點可能無法從 root 抵達，要檢查這些頂點的存在只要從 root 跑一次 DFS 看看有沒有人無法被碰觸到即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4bool visit[100];
5vector<int> adj[100];
6
7void dfs(int v) {
8 visit[v] = true;
9 for (auto u: adj[v])
10 dfs(u);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int a, b, root=0, T=0, parent[100]={0};
15 bool fail = false; map<int, int> m;
16 while (cin >> a >> b && !(a<0 && b<0)) {
17 if (!a && !b) {
18 if (!fail)
19 for (int i=1; i<=m.size(); i++)
20 if (!parent[i]) {
21 if (!root) root = i;
22 else { fail = true; break; }
23 }
24 if (!root && !m.empty()) fail = true;
25 if (!fail) {
26 dfs(root);
27 for (int i=1; i<=m.size(); i++)
28 if (!visit[i])
29 { fail = true; break; }
30 }
31 cout << "Case " << (++T) << " is " << (fail ? "not " : "") << "a tree.\n";
32 fail = false; root = 0; m.clear();
33 memset(visit, false, sizeof visit);
34 memset(parent, 0, sizeof parent);
35 for (int i=1; i<100; i++) adj[i].clear();
36 continue;
37 } else {
38 if (fail) continue;
39 try { m.at(a); } catch (...) { m[a] = m.size() + 1; }
40 try { m.at(b); } catch (...) { m[b] = m.size() + 1; }
41 adj[m[a]].push_back(m[b]);
42 if (parent[m[b]]) fail = true;
43 parent[m[b]] = m[a];
44 }
45 }
46 return 0;
47}