[標準2606][Phothon]ウイルス
質問する
新型ウイルスワームウイルスはネットワークを通じて伝播する.1台のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.
例えば、<図1>に示すように、7台のコンピュータがネットワークに接続されているとする.1番のコンピューターがワームウイルスに感染した場合、ワームウイルスは2番と5番のコンピューターを経て3番と6番のコンピューターに伝播し、2、3、5、6の4台のコンピューターがワームウイルスに感染する.しかし、4番と7番は1番とネットワーク接続がないため、影響を受けません.
ある日、1番のパソコンがワームウイルスに感染した.コンピュータの数とネットワーク上の情報が相互に接続されている場合は、コンピュータを介してワームウイルスに感染したコンピュータの数を出力するプログラムを作成します.
(リンク-https://www.acmicpc.net/problem/2606)
アイデア
コード#コード#
from collections import deque
n = int(input())
t = int(input())
ans = 0
visit = [1]
dic = {}
for i in range(t):
a, b = map(int, input().split())
if a not in dic and b not in dic:
dic[a] = [b]
dic[b] = [a]
elif a not in dic and b in dic:
dic[a] = [b]
dic[b].append(a)
elif a in dic and b not in dic:
dic[a].append(b)
dic[b] = [a]
else:
dic[a].append(b)
dic[b].append(a)
#print(dic)
queue = deque([1])
while queue:
cur = queue.popleft()
ans += 1
if cur in dic:
for i in dic[cur]:
if i not in visit:
queue.append(i)
visit.append(i)
#print(cur, i)
print(ans-1)
Reference
この問題について([標準2606][Phothon]ウイルス), 我々は、より多くの情報をここで見つけました https://velog.io/@record_01/백준-2606python-바이러스テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol