[BOJ]2606-ウィルス

質問リンク

2606-ウイルス

問題の説明

入力

コンピュータ合計

ネットワークに接続するコンピュータ対数

に接続するコンピュータ対

しゅつりょく

1号コンピュータがウイルスに感染すると、ウイルスが感染するコンピュータの数は

である.

問題を解く

前に解決した問題とあまりにも同じですね.
すべてのコンピュータで1番のコンピュータに接続されているコンピュータの数が問題=接続されているリンクの数が問題

深度優先ナビゲーションの使用(DFS)

import sys
input = sys.stdin.readline

def dfs(start, cnt):
    visited[start] = True

    for s in graph[start]:
        if not visited[s]:
            cnt = dfs(s, cnt+1)
    return cnt

computer = int(input())
link = int(input())
graph = [[]for _ in range(computer+1)]
visited = [False for _ in range(computer+1)]
for c in range(link):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
cnt = dfs(1, 0)
print(cnt)