[BFS 알고리즘] 연결 요소의 개수

기출: BOJ #11724

 

일반적인 BFS 문제이다

 

n,m = map(int,input().split())
graph = dict()
visited = [False for _ in range(n+1)]
ans = 0

for i in range(n+1):
    graph[i] = list()

for _ in range(m):
    x, y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def BFS(x):
    visited[x] = True
    queue = [x]
    while queue:
        cur = queue.pop(0)
        for next in graph[cur]:
            if visited[next]: continue
            visited[next] = True
            queue.append(next)

for i in range(1,n+1):
    if visited[i]: continue
    BFS(i)
    ans += 1
    
print(ans)