mingssssss

1.質問

新型ウイルスワームウイルスはネットワークを通じて伝播する.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

2.コード

from collections import deque

N = int(input())
M = int(input())
arr = [list(map(int, input().split())) for _ in range(M)] # 꼭 외워두기!
arr.insert(0, [])
visited = [False for i in range(N+1)]

def bfs(arr):
    answer = 0
    queue = deque()
    queue.append(1)
    while queue:
        v = queue.popleft()
        visited[v] = True
        for x in range(1, M+1):
            if v == arr[x][0]:
                if visited[arr[x][1]] == False:
                    queue.append(arr[x][1])
                    visited[arr[x][1]] = True
                    answer += 1
            if v == arr[x][1]:
                if visited[arr[x][0]] == False:
                    queue.append(arr[x][0])
                    visited[arr[x][0]] = True
                    answer += 1
    return print(answer)
bfs(arr)

3.コメント

初めて1を入れて、巡回して、1に接続されたすべてのノードを探索してカウントして出力します.
他にも多くの良い方法があるが,直感的に理解できないため,最終的にはこのコードで終わる.
しかし,双方向図をより効果的に記述する方法があるかどうかを考察すべきである.
これまで知られていたbfsの動作方式を理解できる良い問題のようだ.
これは何時間も自分で解決した問題なので、とても有意義な問題です.