문제 바로가기

N : 정점의 개수 (1<= N <=1,000)
M : 간선의 개수 (0<= M <=N*(N-1)/2)
(u, v) 간선의 양 끝점을 입력받음.
방향없는 그래프
연결요소의 개수는?

🔍 다른 코드 (DFS, 인접행렬)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())

graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
result = 0


def dfs(v):
    for i in range(1, n+1):
        if graph[v][i] == 1 and not visited[i]:
            visited[i] = True
            dfs(i)


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

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

print(result)

참고 코드 (DFS/인접행렬)

🔍 다른 코드 (DFS, 인접리스트)

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

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

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

def dfs(x):
    visited[x] = True
    for i in graph[x]:
        if not visited[i]:
            dfs(i)


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

print(cnt)

💫 Comment

이전의 DFS/BFS문제에서는 미로탐색과 같은 2차원리스트의 형태였는데 이 문제는 (x,y)와같은 좌표가 아니라 정점x와 같은 형식이라 접근하기 어려웠다.
나의 시도 : 시간초과
노드x의 방문처리를 그래프에서만 표현하려고 했다가 다른 코드를 보고서야 따로 visited리스트를 만들어 체크해주면 된다는걸 알게 되었다.
그래프 구현 방법 : 인접 행렬, 인접 리스트