(Python) - BOJ(11724번) : 연결 요쇼의 개수

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

11724번: 연결 요소의 개수

---

• 문제 : 

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

 

 

 

---

• 풀이 :

그래프를 bfs로 탐색하여 연결 요쇼의 개수를 구해주었습니다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
 
def bfs(start):
    queue = deque()
    queue.append(start)
    while queue:
        D = queue.popleft()
        for i in D:
            if c[i] == -1:
                queue.append(graph[i])
                c[i] = 0
 
if __name__ == "__main__":
 
    N,M = list(map(int,input().split()))
    c = [-1 for _ in range(N + 1)]
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = list(map(int,input().split()))
        graph[b].append(a)
        graph[a].append(b)
    cnt = 0
    for i in range(1,N+1):
        if c[i] == -1:
            c[i] = 0
            bfs(graph[i])
            cnt += 1
    if N == 1:
        print(1)
    else:
        print(cnt)