alan23273850 的刷題筆記
a523: 12442 - Forwarding Emails
Tags: dp, graph, self-thinking-solution
出處：https://zerojudge.tw/ShowProblem?problemid=a523
提交：https://zerojudge.tw/Submissions?problemid=a523&account=allllllan123456
問題：給定 $N\in[2,50000]$ 個人裡面的每位成員分別會把收到的信轉寄給誰，保證每個人都恰好只會把信轉寄給另一個人，那麼請問該交由誰發起寄信的活動，會有最多的人收到信？
解法：
這題最有趣的地方在於每個人都恰好只會把信轉寄給另一個人的這個限制會造成很特殊的拓樸結構，一個特性是從任何一個人往下走訪到最後的足跡所形成的圖形必定是個類似 0 或 6 的形狀，如果起始點已經在一個圓裡面就會像 0，如果不在一個圓裡面就會像 6。於是我們的演算法設計如下，對於一個數字而言，第一次走訪的時候勢必會把底下有圓的部分走過，那麼圓上的每個人可以直接更新這個圓的大小作為答案，如果是圓外的人則是從圓周上慢慢向外遞增作為答案，之後只要再度走訪同樣圖形的時候，遇到有答案的節點便可以直接打住並且把答案往反方向遞增，如此一來每個節點就至多只會存取到兩次，整體的時間複雜度是線性的 $\mathcal O(N)$。
實作技巧的部分，因為每個人的 child 只有一位，便用不到 dfs，可以直接用 stack 模擬，只是這題要記得多用一個陣列 indeX 記錄每個人在 stack 裡面的位置，目的是為了方便偵測圓的出現以及計算其大小。另外在 pop 掉 stack 元素的時候除了順便記得當下參與者的答案之外，也要記得把對應的 indeX 元素歸零，千萬不要在程式碼第 11 行的 for loop 一開始對 indeX 作整體初始化，因為這樣在初始化部分的時間複雜度其實是 $\mathcal O(N^2)$，雖然還是會 AC 可是非常非常不划算，不能每次看到 memset 就當成 $\mathcal O(1)$。
1#include <bits/stdc++.h>
2using namespace std;
3
4int child[50001], indeX[50001], num[50001];
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 int N, T; cin >> T; stack<int> s;
8 for (int z=1; z<=T; z++) { memset(num, 0, sizeof num);
9 cin >> N; int a, b, ans, maX = INT_MIN;
10 for (int i=0; i<N; i++) cin >> a >> b, child[a] = b;
11 for (int i=1; i<=N; i++) { // assert(s.empty());
12 int j = i, indexL = 0;
13 while (!indeX[j] && !num[j]) s.push(j), indeX[j] = ++indexL, j = child[j];
14 if (indeX[j]) {
15 int t = s.size() - indeX[j] + 1;
16 while (s.top() != j) num[s.top()] = t, indeX[s.top()] = 0, s.pop();
17 num[j] = t; indeX[j] = 0; s.pop();
18 }
19 while (!s.empty()) num[s.top()] = num[j] + 1, j = s.top(), indeX[j] = 0, s.pop();
20 if (num[i] > maX) maX = num[i], ans = i;
21 }
22 cout << "Case " << z << ": " << ans << '\n';
23 }
24 return 0;
25}