12442 Forwarding Mail

題目連結

題目敘述

“…所以把這封郵件轉寄給另外十個人，以證明你相信皇帝的新衣。”

這種類別的電子郵件是不是很煩人？
火星人也會收到這類郵件，但他們有一種創新的處理方式。

他們不會隨意或完全不轉寄，而是每次都挑選一位他們認識的對象──恰好一位，不多也不少（且絕不會選自己）──來轉寄這些郵件。
現在，火星部落的酋長想要讓一封郵件開始傳播，但他固執地只想發出一封郵件
作為酋長，他設法查出了誰會將郵件轉寄給誰
他想知道：他應該把郵件先發給哪位火星人，以使看到郵件的火星人數量最大？

輸入

輸入的第一行包含一個整數 T（≤ 20），表示測試案例的數量。

每個測試案例以一行整數 N（2 ≤ N ≤ 50000）開始，表示社群中火星人的數量。
接下來的 N 行中，每行包含兩個整數 u v（1 ≤ u, v ≤ N，u ≠ v），表示火星人 u 會將郵件轉寄給火星人 v。

輸出

對於每個案例，輸出案例編號和一個整數 m
其中 m 是酋長應該發送初始郵件的火星人編號
如果存在多個正確答案，輸出最小的編號

解題思路

直接對所有火星人進行 dfs 來數他們各自能傳給幾個人是不現實的，會花太多時間
我們可以使用一個陣列，將被 dfs 過的火星人能夠使多少人看到信件記錄下來
只要已經有紀錄的我們直接使用紀錄即可，不需要重新 dfs 一遍
並且對每個火星人的 dfs 結果紀錄最大值

程式碼

#include <bits/stdc++.h>
using namespace std;

vector<int> g, vis, cnt;

int dfs(int v) {
    vis[v] = 1; // 標記 v 欲進入 DFS 路徑中
    cnt[v] = 1; // 初始化：至少能見到自己
    // 若下一個轉發目標還未計算過，遞迴呼叫；否則直接利用已知結果
    if (!vis[g[v]]) cnt[v] = dfs(g[v]) + 1; // 若目標節點尚未在當前遞迴路徑被標記，從 g[v] 獲得可見數，再加上當前節點
    vis[v] = 0; // 解除臨時標記，使其他起點的 DFS 可重用此節點
    return cnt[v]; // 回傳計算結果
}

int main() {
    int t, T = 1;
    for (cin >> t; T <= t; T++) {
        cout << "Case " << T << ": "; // 按照題目要求格式輸出
        int n; cin >> n; // 讀取本組測資中的火星人總數 n
        g.assign(n+1, 0); // 1-based indexing，g[u] = v 表示 u 轉發給 v
        cnt.assign(n+1, 0); // cnt[u] 尚未計算時為 0
        vis.assign(n+1, 0); // vis[u] 為遞迴訪問狀態，初值皆為 0
        for (int i = 0; i < n; i++) {
            int a, b; cin >> a >> b; // 輸入資料，火星人 a 轉發給 b
            g[a] = b; // 建立有向邊 a → b
        }

        int ans; // 最佳起點編號
        for (int i = 1, mx = -1e9; i <= n; i++) { // 遍歷所有節點，計算或重用 cnt
            if (!cnt[i]) dfs(i); // 若尚未計算過就執行 DFS，並將結果填入 cnt 陣列
            if (cnt[i] > mx) mx = cnt[i], ans = i; // 更新最大值與對應起點（若並列則保留編號小者）
        }

        cout << ans << '\n'; // 輸出本組測資的最佳起點
    }
}