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

 

 

문제 소개

 

문제

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

 

 

사용한 알고리즘

 

DFS

 

 

 

 

 

 

Code 

 

import sys
import collections

sys.setrecursionlimit(10000)

#sys.stdin = open("input.txt", "r")

input=sys.stdin.readline

N,M = map(int , input().split(" "))

graph = collections.defaultdict(list)

for _ in range(M):
    a,b = map(int , input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

list0 = []
def DFS(startNode:int):
    if startNode in list0:
        return
    else:
        list0.append(startNode)
    for newNode in graph[startNode]:
        DFS(newNode)

connectNode = 0
for k in range(1,N):
    if k not in list0:
        connectNode += 1
        DFS(k)


print(connectNode+N-len(list0))

 

 

 

※ end