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

연결 요소의 개수

문제

• 방향 없는 그래프의 연결 요소 개수를 구하기

입력

• N: 정점의 개수, M: 간선의 개수
• u,v : 간선의 양 끝점
• 같은 간선은 한 번만 주어짐

출력

• 연결 요소의 개수 출력

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())

graph = [[0] * (N+1) for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

answer = 0
visited = [0] * (N+1)

def dfs(V):
    global answer
    visited[V] = 1
    for i in range(1, N+1):
        if visited[i] == 0 and graph[V][i] == 1:
            dfs(i)
    return answer


for i in range(1, N+1):
    if not visited[i]:
        dfs(i)
        answer += 1

print(answer)

• 항상 dfs는 개수 셀 때 헷갈린다...!!!
• 구현만 하면 풀리는 간단한 문제였다 다행 ☺️