boj 11724 : 연결 요소의 개수

문제 주소: https://www.acmicpc.net/problem/11724

난이도: silver 2

1.문제설명

• 무향 그래프가 주어졌을 때, 연결요소의 개수를 구해라

2.문제해결 아이디어.

• 연결요소가 뭔지 나름대로 이해하자면, 서로 연결되지 않은 부분그래프의 개수? 라고 이해했다.
• 그렇다면 bfs로 특정위치에서 방문할수 있는곳을 방문하고
• 연결된 곳을 모두 탐색하자!

3.문제접근법

• bfs로 탐색을 시작하고 탐색한 부분은 visited에 넣어준다.
• 노드를 for문으로 돌며 방문하지 않았다면 bfs를 실행하고, 방문처리해준다.

4.특별히 참고할 사항

• 처음에 시간초과가 나왔다.
• 아무리생각해도 이것보다 더 타이트하게 할 수 없는데 자괴감에 빠져 검색해보니
• input() 대신 sys.stdin.readline으로 하면 해결됐다.
• 앞으로는 그냥 sys.stdin.readline만 써야겠다

5.코드구현

from collections import deque
import sys
input = sys.stdin.readline
N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]
for i in range(E):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

visited = set()
def bfs(graph, start):
    queue = deque([start])
    while queue:
        curNode = queue.popleft()
        for node in graph[curNode]:
            if node not in visited:
                queue.append(node)
                visited.add(node)

cnt = 0
for i in range(1,N+1):
    if i not in visited:
        bfs(graph, i)
        visited.add(i)
        cnt += 1

print(cnt)