UVa 12442 題解 — C++

此筆記為UVa 12442的題目詳解，包含解題思路、C++範例程式碼。

12442 - Forwarding Emails (ZeroJudge a523.)

題目

「…務必轉寄給十個人，以證明你相信國王有新衣。」

這種 email 很討人厭，不是嗎？

火星人也有這種郵件，但他們有個新奇的方式來處理它。他們既不亂寄，也不會不寄，而是只寄給一個朋友，不多也不少，(而且不會寄給自己)。現在火星部落酋長要發一封 email 出去，他很固執只肯發給一個人。身為酋長，他設法查出了誰會轉信給誰，現在他想知道：他的信要寄給誰才能讓最多的火星人看到？

輸入 / 輸出說明

輸入說明	輸出說明
輸入的第一行有一個 T (≤ 20) 表示測資筆數。 每筆測資的第一行有一個整數 N (2 ≤ N ≤ 50000) 表示社群中火星人的數量。以下 N 行每行有兩個整數：u v (1 ≤ u, v ≤ N, u ≠ v) 代表火星人 u 會把 email 轉給火星人 v。	對於每筆測資，印出測資編號及一個整數 m，代表酋長應該把初始郵件寄達的那個火星人。如果正確答案不止一個，輸出最小的數字。

解題思路

這題顯然不能使用陣列儲存 u、v，這邊我選擇使用 map (其實用 vector 可能更好)。

這題使用 dfs 的方式去解，我透過迴圈 j 當起始人出發，但我特別加了 done 這個條件，因為如果有節點在另一個節點的開始到結束的途中，就不必考慮該節點，將該節點也視為已完成遍歷 <註>。

<註> 假設我們有 4 個火星人，而我從 1 出發，途中會送給 2、3，代表有 3 個火星人會收到信，則從 2、3 出發最多的可能也是 3 而已 (因為每個人都只寄給一個人，所以最多的可能就是形成一個環，環內無論從哪點開始都是一樣多人收到信，如下圖一)，而亦有可能小於 3，如下圖二，因此從 2、3 開始不可能比從 1 開始多，所以不必考慮。

圖一

圖二

範例程式碼

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

int n, times;
map<int, int> uv, visit, done; 

int dfs(int node)
{
	visit[node] = 1;  //已訪問此節點 
	done[node] = 1;  //此節點已完成 (若在其他節點中，則必比該節點少，亦算完成) 
	
	times++;
	
	if (visit[uv[node]] == 0)
		dfs(uv[node]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, t, u, v;
	int max, max_index;
	
	cin >> t;
	
	for (i=0;i<t;i++) {
		cin >> n;
		
		uv.clear();
		done.clear();
		
		for (j=0;j<n;j++) {
			cin >> u >> v;
			uv[u] = v;
		}
		
		max = 0;
		max_index = 0;
		
		for (j=1;j<=n;j++) {
			if (done[j] == 0) {
				visit.clear();
				visit[j] = 1;
				
				times = 1;
				dfs(j);
				
				if (times > max) {
				//不需要判斷是不是小於 max_index，因為我是從小的節點到大去找 
					max = times;
					max_index = j;
				}
			}
		}
		
		cout << "Case " << i + 1 << ": " << max_index << endl; 
	}

	return 0;
}

運行結果

AC (0.1s, 10.2MB)

tags: CPE ?星

查看更多資訊請至：https://www.tseng-school.com/