第一屆內壢高中程式挑戰賽題目已公開 - 連結
永久計分板也已公開 - 連結
115 資訊學科能力競賽校內初賽題目已公開 - 連結
115 資訊學科能力競賽北二區複賽模擬賽題目已公開 - 第一場 - 第二場
永久計分板也已公開 - 連結
115 資訊學科能力競賽校內初賽題目已公開 - 連結
115 資訊學科能力競賽北二區複賽模擬賽題目已公開 - 第一場 - 第二場
108 . 馬英九還我牛！
TopCoder
Description
2005年，柯賜海帶著黃牛到總統府抗議，表達對政府政策「開空頭支票（黃牛）」的不滿
抗議後，他將牛隻帶到二二八公園水池洗澡，違反《水利法》遭台北市政府開罰與沒收牛隻
之後，柯賜海多次在媒體前向當時的台北市長馬英九抗議，大喊「馬英九，還我牛！」
於是這便成為當時的迷因之一
「馬英九，還我牛！」在社群平台上開始流傳。平台將使用者視為節點，若兩名使用者互相追蹤，則迷因可以從一人傳到另一人。
總共有 $N$ 位使用者，彼此之間互相追蹤的共有 $M$ 組。
一開始只有編號為 $1$ 的那位知道這個迷因。每經過一輪，所有已知道迷因的使用者會將訊息傳給尚未收到訊息的好友。
給定社群網路以及傳播輪數 $K$，則經過 $K$ 輪後，共有多少人知道這個迷因。
如範例一，我們可以畫出
如圖，
當 $K = 0$ 時，知道迷因的人有 ${1}$，共 $1$ 人
當 $K = 1$ 時，知道迷因的人有 ${1 ,\ 2 ,\ 4 ,\ 7 ,\ 10}$，共 $5$ 人
當 $K = 2$ 時，知道迷因的人有 ${1 ,\ 2 ,\ 3 ,\ 4 ,\ 5 ,\ 6 ,\ 7 ,\ 9 ,\ 10}$，共 $9$ 人
輸出為 9。
對於所有測試資料：
$1 \le N \le 10$$6$
$1 \le M \le 10$$6$
$0 \le K \le 2 \times 10$$5$
Input Format
輸入共 $1 + M $ 行，
第一行共 $3$ 個整數 $N ,\ M ,\ K$；
接下來有 $M$ 行，
第 $1 + i$ 行表示第 $i$ 對互相追蹤的使用者編號。
Output Format
輸出僅一行，
共 $1$ 個整數，表示 $K$ 天後知道迷因的人數。
Sample Input 1
5 4 5 1 2 2 3 3 4 4 5
Sample Output 1
5
Sample Input 2
10 15 2 1 7 2 9 3 8 1 4 5 10 2 6 1 2 4 9 3 5 6 8 7 10 2 3 4 6 1 10 5 7
Sample Output 2
9
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~4 | $N \le 100$、$M \le 500$ 且 $K \le N$ | 16 |
| 3 | 2, 5 | $K = 0$ | 2 |
| 4 | 3, 6 | $K = 1$ | 2 |
| 5 | 5~8 | $N \le 10$$3$ 且 $M \le 2 \times 10$$3$ | 20 |
| 6 | 9~15 | 題目範圍限制 | 60 |