BOJ 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724
시간 3초, 메모리 215MB
input :

• N M (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• u v(1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만

output :

• 연결 요소의 개수를 출력한다.

---

무방향 그래프? 양방향 그래프와 동일한 것 같다.

visit 리스트에 False가 남아 있냐로 구분하면 된다.
그리고 graph를 저장 할 때도 0을 빼고 시작 했기 때문에 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)