[白俊]2606号:ウイルス

質問する

新型ウイルスワームウイルスはネットワークを通じて伝播する.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番に属する接続素子のノード数を求めることができる.これは、DFSの起点を1番コンピュータとし、1番コンピュータに接続されたすべてのノードにアクセスし、infection += 1を行う.このため、infectionをグローバル変数として処理する.

import sys

# 그래프 안의 연결 컴포넌트 중 하나의 노드만 바이러스에 걸려도
# 연결 컴포넌트에 속하는 모든 노드가 바이러스에 감염된다.

# 1번 컴퓨터가 웜 바이러스에 걸렸다.
# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수?

infection = -1

def dfs(graph, v, visited):
    visited[v] = True
    global infection
    infection += 1
    for i in graph[v]:
        if (not visited[i]):
            dfs(graph, i, visited)

N = int(sys.stdin.readline())
E = int(sys.stdin.readline())

graph = [ [] for x in range(N+1) ]
visited = [ False ] * (N+1)

for i in range(E):
    u, v = map(int, sys.stdin.readline().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

dfs(graph, 1, visited)

print(infection)