題目： UVa - 615 - Is It A Tree?

題目說明

給一個有向圖，求該圖是否是一個 Tree。

根據題目的敘述，Tree 需要滿足以下三個條件:

  • 只有一個沒有被其他節點接入的節點，稱為 root
  • 除了 root 以外的所有節點，都只會被一個邊接入
  • 從根到任一節點，都只有一條唯一的路徑

Input： 每組測資包含許多組邊，每組邊以兩個整數表示，u、v 表示有一條 u 指向 v 的邊，若為 0 0 表示此組測資結束，若一組測資以 -1 -1 開始表示程式結束。

Output： 輸出該組測資是否是一個 Tree。

解題思路

建圖，先判斷是否沒有任何節點，若沒有任何節點也是 Tree，否則隨便挑一個沒有被接入的節點開始 DFS 判斷是否有環，最後判斷是否所有節點都有被遍歷到即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int u, v;
unordered_map<int, vector<int>> G;
unordered_map<int, int> inDegree;
unordered_set<int> visited;

void init()
{
    G.clear();
    inDegree.clear();
    visited.clear();
}

void readGraph()
{
    while (!(!u && !v))
    {
        G[u].push_back(v);
        inDegree[u] += 0;
        ++inDegree[v];
        cin >> u >> v;
    }
}

// 如果有環則回傳 false
bool dfs(int u)
{
    visited.insert(u);
    for (auto& v : G[u])
    {
        if (visited.count(v)) return false; // 有環
        if (!dfs(v)) return false;
    }
    return true;
}

bool solve()
{
    // 沒有節點也是樹
    if (inDegree.empty()) return true;

    for (auto& [u, deg] : inDegree)
    {
        if (deg) continue;
        if (!dfs(u)) return false;
        break;
    }

    // 檢查是否有節點還沒有遍歷過
    for (auto& [u, _] : inDegree)
        if (!visited.count(u)) return false;
    return true;
}

int main()
{
    int Case = 0;
    while (cin >> u >> v && !(u == -1 && v == -1))
    {
        init();
        readGraph();
        
        cout << "Case " << ++Case << " is ";
        if (solve()) cout << "a tree.\n";
        else cout << "not a tree.\n";
    }
}

參考資料

c131. 00615 - Is It A Tree? - 高中生程式解題系統