[BOJ]2606-ウィルス

4903 ワード
python アルゴリズム#アルゴリズム# boj グラフィックの参照 テキストリンク

質問リンク


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)
    Golang学習ノート-テスト
    Backjun 1676[工場0の個数|python]