白準2606号:ウイルス

5560 ワード
テキストリンク
2606号:ウイルス

問題の説明
  • のコンピュータがワームウイルスに感染した場合、ネットワークに接続されているすべてのコンピュータがワームウイルスに感染します.(グラフィックの問題)
  • 第1行目は、コンピュータ数(100台以下)
    • を含む.
  • 第2行がネットワークに直接接続するコンピュータ対数
    • 問題を解く
  • DFS VS BFS:BFSはDFSを使用しなくても速度が速くなると予想されます(DFSを使用しない場合は、より速いBFSを使用します!)
  • BFS:常にDEQUE->popleft()を念頭に置き、dequeにより上位レベルのノードを追加し、距離などの条件で追加!
  • アクセスリスト:ノードと比較して、N+1の設定はノードの名前に依存しますが、通常はノードが1から始まるため、(N+1)スペース
    • が作成されます.
  • グラフィック:双方向グラフィック!常に連絡を保つ
    • from collections import deque, defaultdict

def bfs(graph,start,visited):
    visited[start] = True

    new_computer = deque([start])

    while new_computer:
        computers = new_computer.popleft()

        for computer in graph[computers]:
            if not visited[computer]:
                new_computer.append(computer)
                visited[computer] = True

N = int(input())
M = int(input())
visited = [False] * (N+1)

graph = defaultdict(list)
for _ in range(M):
    i,j = list(map(int,input().split()))
    graph[i].append(j)
    graph[j].append(i)

bfs(graph,1,visited)
print(sum(visited)-1)
    JavaScriptによるStackの実装
    [2020ココアブラインド]移動ブロック