[백준 11724 파이썬] 연결 요소의 개수

https://www.acmicpc.net/problem/11724

연결 요소란?

위 그림은 하나의 그래프에 두 개의 연결 요소를 가진다.

연결 요소의 조건

1. 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
2. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

# 연결 요소의 개수

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().rstrip().split()) # 정점, 간선
graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)

def bfs(start):
    deq = deque([start])
    visited[start] = True

    while deq:
        node = deq.popleft()
        
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                deq.append(next_node)
        
count = 0

for i in range(1, N + 1):
    if not visited[i]:  # 만약 방문하지 않았다면
        if not graph[i]:  # 만약 그래프가 비어있다면
            count += 1  # 연결요소 1개 추가
            visited[i] = True  # 방문 처리
        else:  # 만약 그래프가 비어있지 않다면(어느 점과 연결된 점이 있다면)
            bfs(i)  # 해당 i를 시작노드로 bfs를 돈다. bfs가 끝나면 연결요소의 방문이 끝난거다.
            count += 1  # 연결요소 +1개 해준다.

print(count)

bfs가 끝나면 시작지점의 연결요소 방문이 끝 -> 연결요소 +1

참고
https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component
https://ji-gwang.tistory.com/292