# 題目: UVa 12442 - Forwarding Emails

# 題目說明

一個小鎮裡面，每一個人都會寄信給另外一個人
求第一封信寄給誰能讓最多人看到

---

INPUT:
第一行有一個整數T，代表有T筆測資
每筆測資第一行有一個整數N，代表人數
接下來有N行，每行有兩個整數u和v，代表u寄信給v

---

OUTPUT:
輸出第一封信寄給誰能讓最多人看到
(如果數量一樣則取編號小的)

# 解題方法

跑dfs，儲存寄信數量及第一個人的編號
接著判斷是否為最大數量

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

vector<int> sent;
vector<bool> check, sum;
int times;

void dfs(int num)
{
	++times;
	sum[num] = check[num] = true;
	if (!check[sent[num]]) dfs(sent[num]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T, N;
	cin >> T;

	for (int i = 1; i <= T; ++i) {

		cin >> N;
		sent.assign(N + 1, -1);
		sum.assign(N + 1, false);

		for (int j = 0, a, b; j < N; ++j) cin >> a >> b, sent[a] = b;
		
		int ftimes = 1;
		int fnum = sent[0];

		for (int j = 1; j <= N; ++j)
			if (!sum[j]) {

				check.assign(N + 1, false);
				check[j] = true;
				times = 1;

				dfs(sent[j]);

				if (times > ftimes || (times == ftimes && j < fnum))
					fnum = j, ftimes = times;
			}

		cout << "Case " << i << ": " << fnum << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2012442/