b218: 3. 找關鍵人物
Tags :
Accepted rate : 128人/144人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-03-17 23:23

Content

問題敘述:
  社會學家在研究一個社群時,常會用一個圖形 (graph) 來表示組成該社群人員之間的關係結構。一個標準的表示方式是:社群中每一個成員用圖形的一個頂點 (vertex) 來表示,而社群中的兩個人若有一特定關係則在這兩人相對的頂點間加一個邊 (edge) 來表示這個關係。而有了這樣的圖形表示法,社會學家就可以就這圖形的結構來進行一些研究。
 有一種研究是要在社群中找關鍵人物,有關關鍵人物的認定有各式各樣的方式,其中有一種理論認為一個人若是一個關鍵人物那麼在社群中的很多聯繫都要透過這個人才能完成。因此基於這個觀點,有人提出一個假說:一個人若是一個關鍵人物,那麼他在社群關係圖形中相對的頂點就會有最多條最短路徑( shortest path) 通過。
     現有一個社會學家想要檢測這個理論的正確性,因此他希望你能寫個程式幫他找到社群中的可能關鍵人物。很湊巧的這社會學家找來的社群關係圖形都是樹狀的。我們都知道在樹狀圖 (tree) 中任何兩個頂點間只有唯一一條路徑,因此這路徑當然就是最短路徑。舉例來說,考慮以下樹狀圖:

 

這個圖形共有 8 個頂點,編號從 1 到 8。任何兩個頂點間都有一條路徑,因此這圖形共有 28 條路徑。頂點 1、2、6、7、8 是樹葉節點,因此沒有任何路徑通過。點 3 及頂點 5 分別都有 11 條路徑通過,而頂點 4 則有 15 條路徑通過,因此根這個理論頂點 4 所代表的人物就是關鍵人物,而此點也稱為此圖的關鍵頂點。

Input
輸入內容的第一行只有一個數字 n,代表輸入樹狀圖的頂點數。後面會接 n-1 行數字,每一行有兩個數字以空白隔開,代表該圖一個邊的兩個頂點,頂點的編號從 1 到 n。測詴資料中 n 的可能最大值為 20000.
Output
輸出一行以空白隔開的兩個數字,第一個數字為所找到關鍵頂點的編號,若好幾個頂點符合要求,請輸出編號最小的。第二個數字為通過該節點的路徑數。
Sample Input
輸入範例1:
8
1 3
3 4
5 4
6 5
8 4
5 7
2 3
輸入範例2:
6
1 5
2 5
5 4
4 6
3 4
Sample Output
輸出範例1:
4 15
輸出範例2:
4 7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
Hint :
感謝ck99126提出範例輸入有誤!
Tags:
出處:
97學年度全國資訊學科能力競賽


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」