문제 : https://www.acmicpc.net/problem/16947

풀이

그래프를 탐색하면서 cycle을 찾지 않아도 풀이가 가능하다.

빨간색 동그라미에 주목하면 다음과 같은 사실을 알 수 있다.

• 사이클에 포함되지 않은 노드의 끝은 1개의 간선만을 갖는다.

• 사이클에 포함된 노드가 사이클에 포함되지 않은 노드와 만날 때, 간선은 최소 3개 이상이다.

1개의 간선을 갖는 노드를 지워버리면
다음 노드(부모 노드) 역시 간선을 하나만 갖게 된다.

부모 노드가 사이클에 포함된 노드라면,
지워져도 2개 이상의 간선이 남는다.

그래프

※ 그림에 실수로 표시를 못했는데 6번 노드의 간선 수는 0이다.

그림과 같은 간선이 있을 때 간선 수가 1개인 노드를 찾아제거한다.

제거하는 노드와 연결된 노드가 부모 노드가 된다.

부모 노드인 5번 노드의 간선 수가 1이 되었으므로, 역시 제거한다.

간선 수가 1인 노드가 더이상 남아있지 않아 제거할 노드가 없다.

이제 부모노드가 -1인 노드는 모두 사이클에 속한 노드이므로, 거리가 0이다.
5번 노드는 부모 노드인 2번 노드+1의 거리를 갖고
6번 노드는 부모 노드인 5번 노드+1의 거리를 갖는다.

최종적으로 [0, 0, 0, 0, 1, 2]가 답안이 된다.

코드

import sys
from collections import deque
input = sys.stdin.readline

# 사이클에 속한 노드부터 BFS 탐색으로 나머지 노드의 거리를 구함
def BFS():
    que = deque()

    for i in range(N):
        if parents[i] == -1:
            answer[i] = 0
            que.append(i)

    while que:
        current = que.popleft()

        for child in graph[current]:
            if answer[child] == -1:
                answer[child] = answer[current] + 1
                que.append(child)


N = int(input())
# 입력받은 그래프 저장
graph = [[] for _ in range(N)]
# graph는 추후 BFS 탐색때 사용해야하므로, 노드를 제거할 별도의 그래프
temp = [[] for _ in range(N)]
# 간선 수를 저장할 변수
graph_size = [0] * N
# 부모 노드를 저장할 변수
parents = [-1] * N
# 출력될 답을 저장할 변수 (거리)
answer = [-1] * N

# 입력 처리
for _ in range(N):
    s1, s2 = map(int, input().split())
    graph[s1-1].append(s2-1)
    temp[s1-1].append(s2-1)
    graph_size[s1-1] += 1
    graph[s2-1].append(s1-1)
    temp[s2-1].append(s1-1)
    graph_size[s2-1] += 1

# 전체 탐색 후 간선 수가 1인 노드가 발견되지 않으면 반복 종료
while True:
    flag = True
    for i in range(N):
        if graph_size[i] == 1:
            parent = temp[i].pop()
            parents[i] = parent
            temp[parent].remove(i)
            graph_size[i] = 0
            graph_size[parent] -= 1
            flag = False

    if flag:
        break

BFS()

print(*answer)