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

문제 보기

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

11724번: 연결 요소의 개수

문제 해결

그래프를 직접 그려보면서 문제를 해결하면 된다. 그래프를 그리다가 모든 노드가 한 번에 이어지면 연결 요소는 1개이다.

1번 예제는 (1,2,5) (3,4,6) 2개

2번 예제는 (1,2,3,4,5,6) 1개

 

소스 코드

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

n, m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n+1)
def bfs(x):
    q = deque()
    q.append(x)
    visited[x] = True
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

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

print(cnt)