BOJ 11724接続要素の数

6190 ワード
2021.01.16 テキストリンク
https://www.acmicpc.net/problem/11724
3秒、215 MBメモリ
input :
  • N M (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
  • uv(1≦u,v≦N,u≠v)のような幹線は1回
    • しかかかりません
    output :
  • 接続要素の個数を出力します.
    • 方向図なし?
    双方向図と同じようです.
    アクセスリストでFalseがあるかどうかを区別するだけです.
    またgraphの保存もゼロから始まるので、for文でBFSを返す場合(1,n+1)回.
    import sys
from _collections import deque

n, m= map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def BFS(start):
    q = deque([start])
    visit[start] = True

    while q:
        now = q.popleft()

        for i in graph[now]:
            if not visit[i]:
                q.append(i)
                visit[i] = True
    return cnt

visit = [False] * (n + 1)
visit[0] = True
cnt = 0
for i in range(1, n + 1):
    if not visit[i]:
        BFS(i)
        cnt += 1
print(cnt)
    演算子
    [プログラマー]牛乳とヨーグルトがいっぱい入ったショッピングバスケット(MySQL)