99클럽 코테 스터디 4일차 TIL + dfs (깊이우선탐색)

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

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

n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
seq = 1 # 방문순서

def dfs(r):
    global seq
    visited[r] = seq
    graph[r].sort()
    for i in graph[r]:
        if visited[i] == 0:
            seq += 1
            dfs(i)

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

dfs(r)
for i in range(1, n+1):
    print(visited[i])

• 정점 u,v 가 양방향 간선 이기 때문에 u와 v에 각각 append 해준다.
• 방문 순서를 출력해야 하기 때문에 방문순서 seq와 visited[] 를 사용한다.
• 인접 정점은 오름차순으로 방문해야 하기 때문에 정점 u에 인접한 접점들을 방문하기 전에 정렬해준다.
• 방문하지 않았다면 방문순서를 더해주며 visited[] 에 초기화 해준다.