[Graph] 연결 요소의 개수

박고은·2023년 5월 23일
0

알고리즘

목록 보기
10/12

import sys

N, M = map(int, sys.stdin.readline().split())
nodes = [[0 for _ in range(N+1)] for _ in range(N+1)]

for m in range(M):
    a, b = map(int, sys.stdin.readline().split())
    nodes[a][b] = 1
    nodes[b][a] = 1

visited = []
count = 0

def DFS(n):
    visited.append(n)
    for i in range(1, N+1):
        if nodes[n][i]==1 and i not in visited: DFS(i)

for i in range(1, N+1):
    if i not in visited:
        DFS(i)
        count += 1

print(count)

연결 노드를 2차원으로 표현
모든 연결 노드를 방문하는 문제 -> DFS

0개의 댓글