[백준] 11724. 연결 요소의 개수

문제 설명

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

제한사항

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
첫째 줄에 연결 요소의 개수를 출력한다.

풀이

활용개념 : bfs

#연결 요소의 개수

from collections import deque
import sys

def bfs(v):
    global ans
    Q = deque()
    Q.append(v)
    visited[v] = 1

    while Q:
        v = Q.popleft()
        
        for w in range(1,V+1):
            if adj[v][w] == 1 and visited[w] == 0:
                Q.append(w)
                visited[w] = 1
    

V,E = map(int, sys.stdin.readline().split())


adj = [[0] * (V+1) for i in range(V+1)]
for i in range(E):
    s, e = map(int, sys.stdin.readline().split())
    adj[s][e] = adj[e][s] = 1

visited = [0] * (V+1)

cnt = 0
for i in range(1,V+1):
    if not visited[i]:
        bfs(i)
        cnt += 1

print(cnt)