연결 요소의 개수

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

 

나의 풀이

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

a, b = map(int, input().rstrip().split())

visit = [0]*a
conn_dict = {i: [] for i in range(1, a+1)}

for _ in range(b):
    s, e = map(int, input().rstrip().split())
    conn_dict[s].append(e)
    conn_dict[e].append(s)

result_ct = 0
for i in range(1, a+1):
    if visit[i-1] == 0:
        result_ct += 1
        queue = deque([i])
        while queue:
            now_v = queue.popleft()
            visit[now_v-1] = 1
            
            for next_v in conn_dict[now_v]:
                if (visit[next_v-1] == 0) and (next_v not in queue):
                    queue.append(next_v)
print(result_ct)

 

시간 복잡도

conn_dict = {i: [] for i in range(1, a+1)} : 연결정보 생성 ( 선형 시간 복잡도 )
for _ in range(b) : 연결정보 생성 ( 선형 시간 복잡도 )
for i in range(1, a+1) : BFS 탐색 ( 선형 시간 복잡도 )
    if visit[i-1] == 0:
        result_ct += 1
        queue = deque([i])
        while queue:
해당 알고리즘은 선형 시간 복잡도 : O(n)