題目： UVa - 12442 - Forwarding Emails

題目說明

有一個小鎮，裡面的居民每個人都只會給另一個人寄信，求把信寄給哪位居民可以讓最多人看到這封信，若有相同者則取較小者。

Input： 第一行為一整數 T，代表有 T 組測資，每組測資的第一行為一整數 N，接下來 N 行每行都有兩個整數 u、v，代表居民 u 會把信寄給居民 v。

Output： 輸出寄信給誰可以讓最多的居民看到這封信，若有相同者則取較小者。

解題思路

DFS 模擬即可，由於會 TLE，所以進行一點剪枝，多使用一個陣列紀錄某位居民是否已經被模擬過了，若在前面被模擬過了則就不需要在模擬第一個寄信給這位居民了，因為前面模擬的是另一個居民會寄給這位居民，一定會比直接寄信給這位居民的人數還要多。例如：

1
2
3
4
5
6
7
8
若居民有 3 人，且寄信關係為：

1 3
2 3
3 2

則寄信給第一位居民時會再寄給第三位居民，那遍歷到第三位居民時就不需要在模擬一次了，
因為由第一位寄給第三位，一定會比直接寄給第三位多。

參考解法

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
#include <iostream>
#include <functional>
#include <climits>
#include <vector>

#define LOOP(n) for(int I = 0; I < n; ++I)

using namespace std;

// reference: https://ppt.cc/fXuBwx

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

int main()
{
    int T;
    cin >> T;

    LOOP(T)
    {
        int N;
        cin >> N;

        vector<int> adj(N + 1);
        LOOP(N)
        {
            int u, v;
            cin >> u >> v;
            adj[u] = v;
        }

        int _max = INT_MIN, ret = 0;
        vector<bool> visited(N + 1), dfsV;

        function<int(int)> dfs = [&](int u) -> int
        {
            // 如果已經寄過了就直接回傳，避免環
            if (dfsV[u]) return 0;
            visited[u] = dfsV[u] = true;
            return 1 + dfs(adj[u]);
        };

        for (int i = 1; i <= N; ++i)
        {
            // 如果 i 在前面被做過一次那就不用再做一次了，因為前面是從某個人寄到 i，
            // 一定會比直接寄到 i 還要多人
            if (visited[i]) continue;

            dfsV.assign(N + 1, false);
            int tmp = dfs(i);
            if (tmp > _max) _max = tmp, ret = i;
        }

        cout << "Case " << I + 1 << ": " << ret << '\n';
    }
}

參考資料

[UVA] 12442 - Forwarding Emails