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

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

11724번: 연결 요소의 개수

 

그래프 문제를 많이 풀어본적이 없어서 구현을 어떻게 해야할지 애를 많이 썻던 문제

 

아이디어

 

간선의 개수를 gragh 리스트에 전부 저장을 해준 뒤 방문 유무를 체크하면서 BFS로 색칠을 해준다. 그 후 cnt값을 계속 증가시키면서 최종 cnt를 출력하는 방식으로 구현하였다. 

 

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

arr = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

check = [False] * (n+1)
cnt = 0

for i in range(1, n+1):
    if not check[i]:
        dq = deque()
        dq.append(i)
        check[i] = True
        while dq:
            node = dq.popleft()
            for i in arr[node]:
                if not check[i]:
                    check[i] = True
                    dq.append(i)
        cnt+=1

print(cnt)

 

완성