Python/DFS BOJ-11724 연결요소의 개수

Posted on | In

[Python/DFS] BOJ-11724 연결요소의 개수

📌문제링크

분리된 그래프의 개수를 세면 된다.

DFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(i):
    visited[i]=1
    for b in board[i]:
        if visited[b]==0:
            dfs(b)

if __name__ =='__main__' :
    N,M = map(int,input().split())
    board =[[] for _ in range(N)]
    visited = [0]*N
    for i in range(M):
        x,y = map(int,input().split())
        board[x-1].append(y-1)
        board[y-1].append(x-1)
    cnt=0
    for i in range(N):
        if visited[i]==0:
            dfs(i)
            cnt +=1
    print(cnt)