백준 11724 연결 요소의 개수 Python

🐸 문제 정보

11724번: 연결 요소의 개수

 

🤖 알고리즘

DFS

 

⏱️ 풀이 시간

07.51m

 

📝 풀이

MST 같아 보이지만 DFS 문제이다.

입력 값을 바탕으로 양방향 그래프를 만들어주고, 방문했는지 체크할 visited도 만든다.

이후 그래프를 돌면서, 연결된 노드는 모두 방문처리하고, 방문하지 않은 노드에서 다시 dfs를 시작할 경우 결과 값에 1 더해준다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m = list(map(int, input().rstrip().split()))
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
res = 0

for _ in range(m):
    u, v = list(map(int, input().rstrip().split()))
    graph[u].append(v)
    graph[v].append(u)

def dfs(v):
    visited[v] = True
    for node in graph[v]:
        if not visited[node]:
            dfs(node)

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

print(res)