[問題解決]Back-2606ウイルス(dfsおよびbfs)
5764 ワード
提问链接
問題の説明
新型ウイルスワームウイルスはネットワークを通じて伝播する.1台のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.
例えば、<図1>に示すように、7台のコンピュータがネットワークに接続されているとする.1番のコンピューターがワームウイルスに感染した場合、ワームウイルスは2番と5番のコンピューターを経て3番と6番のコンピューターに伝播し、2、3、5、6の4台のコンピューターがワームウイルスに感染する.しかし、4番と7番は1番とネットワーク接続がないため、影響を受けません.
ある日、1番のパソコンがワームウイルスに感染した.コンピュータの数とネットワーク上の情報が相互に接続されている場合は、コンピュータを介してワームウイルスに感染したコンピュータの数を出力するプログラムを作成します.
入力
最初の行はコンピュータの数を示します.パソコンの数は100以下で、1台あたり1番から順番に番号をつけます.2行目は、ネットワークに直接接続されているコンピュータペアの数を示します.次に、ネットワークに直接接続された各行の1対のコンピュータの番号ペアが与えられる.
しゅつりょく
1番コンピュータがワームウイルスに感染した場合、1番コンピュータを介してワームウイルスに感染したコンピュータの数を1行目に出力する.
入力例1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
サンプル出力1
4
私の答え
これは簡単な問題だ.dfsで解決しました.彼らは四半期を探求するからだ.
dfs再帰と隣接リストを用いた.
隣接リストを使用する場合、注意すべき部分は無方向図です.
なぜなら、方向図であれば、再帰を使用する場合、戻る道は存在しないからである.
コード#コード#
def dfs(graph, v, visited):
visited[v] = 1
for i in graph[v]:
if visited[i]==0:
dfs(graph,i, visited)
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1) ]
for _ in range(m):
a, b = map(int, input().split()) # 방향 없음
graph[a].append(b)
graph[b].append(a)
# print(graph)
visited= [0]*(n+1)
dfs(graph, 1, visited)
cnt = 0
for i in visited:
if i==1:
cnt+=1
print(cnt-1)
Reference
この問題について([問題解決]Back-2606ウイルス(dfsおよびbfs)), 我々は、より多くの情報をここで見つけました https://velog.io/@redcarrot01/ProblemSolving-백준-2606-바이러스-구현テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol