s458.
pC. 蠕蟲病毒(Cyberattack)
內容
蠕蟲病毒是一種具備自我複製能力的惡意程式。
已知有 N 個人，以及 M 組雙向連線關係 (u, v)，表示 u 與 v 可以互相傳遞資料。其中保證任意兩人之間皆可透過若干條連線互相到達。
最初共有 A 個人遭到蠕蟲病毒感染，編號為 s1, s2, ..., sA，這些人視為在第 0 天已被感染。
在第 k 天被感染的人，會於第 k+1 天感染所有尚未感染且與其直接相連的人，而已感染過的人不會再次被感染。
請問至少需要幾天，所有 N 個人才會皆被感染？
以下圖為例，假設最初蠕蟲感染 {0, 8}，則經過 2 天後，所有人皆被感染。
輸入說明
第一行有兩個正整數 N 和 M，代表總共有 N 個人(編號 0 ~ N-1)、M 組雙向連線關係
1 ≤ N, M ≤ 104
接著有 M 行，每行有兩個非負整數 u 和 v，代表節點 u 和節點 v 直接相連
保證所有測資皆不會有重邊發生
0 ≤ u, v ≤ N-1，並且 u ≠ v
最後一行有 A+1 個非負整數，格式為 A s1 s2 ... sA
代表有 A 個初始感染者，與每個初始感染者編號 si
1 ≤ A ≤ 10
0 ≤ si ≤ N-1
輸出說明
至少需要幾天，所有 N 個人才會皆被感染
範例輸入
#1
9 10 0 1 0 3 0 5 2 4 3 4 3 6 4 8 5 6 6 7 6 8 2 0 8
範例輸出
#1
2
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1M
公開 測資點#4 (5%): 2.0s , <1M
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
提示 ：
10%：為直鏈，即相連關係為 (0, 1), (1, 2), ..., (N-2, N-1)
20%：每個人最多只會和兩個人相連
30%：A = 1
40%：無特別限制
標籤:
出處:
115學年度
hgsh
校內賽
[管理者：
mushroom.cs9
...
(mushroom)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||