[Baekjoon] Graph - 24479 알고리즘 수업 - 깊이 우선 탐색 1

문제

https://www.acmicpc.net/problem/24479

 

풀이

그래프 탐색 이용

1. 정점 번호 오름차순 정렬

2. DFS 를 이용한 풀이

3. python 함수 호출 수 제한 변경

 

예시

5 5 1
1 4
1 2
2 3
2 4
3 4

 

 

 

코드

import sys

sys.setrecursionlimit(130000)

n, m, r = map(int, sys.stdin.readline().rstrip().split())
edges = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    edges[x].append(y)
    edges[y].append(x)


for edge in edges:
    edge.sort()

index = 1

def dfs(r):
    global index
    visited[r] = index

    for v in edges[r]:
        if not visited[v]:
            index += 1
            visited[v] = index
            dfs(v)

dfs(r)
print(*visited[1:], sep="\n")