백준 2606

import sys


def dfs(x):
    global count
    visit[x] = 1
    for next in graph[x]:
        if visit[next] == 0:
            count += 1
            dfs(next)


n = int(sys.stdin.readline())
graph = [[] * (n + 1) for _ in range(n + 1)]
visit = [0] * (n + 1)
for _ in range(1, int(sys.stdin.readline()) + 1):
    i, j = map(int, sys.stdin.readline().split())
    graph[i].append(j)
    graph[j].append(i)

count = 0
dfs(1)
print(count)

백준 11725

방문 체크를 parent 배열 하나로 체크해도 될듯?

import sys
sys.setrecursionlimit(10**6)


def dfs(x):
    visit[x] = 1

    for next in graph[x]:
        if visit[next] == 0:
            visit[next] = 1
            parent[next] = x
            dfs(next)


n = int(sys.stdin.readline())
graph = [[] * (n + 1) for _ in range(n + 1)]
parent = [0, 1] + [0] * (n - 1)
visit = [0] * (n + 1)
for _ in range(1, n):
    i, j = map(int, sys.stdin.readline().split())
    graph[i].append(j)
    graph[j].append(i)

dfs(1)
# print(parent)
for k in range(2, n + 1):
    print(parent[k])