UVa12442 - Forwarding Emails(DFS)

題目大意

有一封信需要給大家知道，而每一個人都會將信轉寄給另外一個人(不會轉寄給第二個人)，你必須找出寄給誰才可以讓最多的人知道。

請輸出，從誰開始轉寄可以讓最多人知道。
題目連結

重點觀念

• DFS 概念轉換

分析

• 由於題目有說明每一個人只會轉寄給另外一個人，那我們的目標就是知道每一個人他不斷往下轉寄後，最多可以轉寄給幾個人
• 因此直接使用 DFS 實作
• 因為不可能每一個人都 DFS，會 TLE，因此優化
  • 舉例： A 給 B，B 給 C，C 給 D
  • 那我們如果從 B 開始寄信，那麼 C、D 我們是不是也知道他最多可以轉寄給幾個人(DFS特性)
  • 因此只要 DFS 跑過的，我們就不需要再跑一次。
  • 但是假如接下來我們跑 A，那我們是不是就直接找出 B 最多轉寄 3 個？
    • 不行，要注意迴圈問題
    • 舉例：A 給 B，B 給 C，C 給 A，D 給 A
    • 如果從 C 開始跑，那順序會是 C -> A -> B。
    • 此時再來從 D 繼續跑，那 D 碰到 A，直接收到 A 最多轉寄兩個，輸出答案
    • 但其實不對，從 D 開始跑，可以轉寄給四個
• 為了避免 DFS 拓樸排序的問題，因此我們只能保證知道 DFS 的節點，最多可以轉寄幾個，但沒辦法確認沒有被 DFS 的節點碰到有被 DFS 過的節點，此時，有被 DFS 過的節點最多轉寄的信已經被我們求出。

參考連結

uva 12442 Forwarding Emails by nur-shuvo

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 50020
#define int long long
using namespace std;
int t, n, kase = 0;
int a, b, cnt;
vector<int> edge[MAXN];
int visit[MAXN], flag[MAXN];

void dfs(int root){
    if(visit[root]) return; //有被經過，因此不再重複
    visit[root] = 1; 
    for(int it : edge[root]){
        dfs(it);
        cnt++; //紀錄總長度
    }
    //由於只能轉寄給一個人，因此從起點到 root 只有一種路徑，經過後就不會再重複經過。
    //但有可能這個路徑本身是 circle，但不會出現兩個以上 circle，因此不會發生衝突。
    //如果有兩個以上 circle 表示，會有一個人可以轉寄給兩個人
    visit[root] = 0; 
    flag[root] = 1; //分析 2-1,2-2,2-3,4
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++) edge[i].clear(); //清除資料

        for(int i = 0; i < n; i++){
            cin >> a >> b;
            edge[a].push_back(b); //加入邊
        }

        memset(visit, 0, sizeof(visit));
        memset(flag, 0, sizeof(flag));
        int ans = 0, ans_cnt = 0; //ans 是從誰寄信最好，ans_cnt 則是最多可以轉寄給幾個人

        for(int i = 1; i <= n; i++){
            if(flag[i]) continue;
            cnt = 0;
            dfs(i);
            if(ans_cnt < cnt){ //如果現在的答案比較大，就替換他
                ans = i;
                ans_cnt = cnt;
            }
        }
        cout << "Case " << ++kase << ": " << ans << "\n";

    }
    return 0;
}