백준 16947 - 서울 지하철 2호선 (C++)

문제 문제 링크 BOJ 16947 - 서울 지하철 2호선 문제 요약 $N$개의 정점과 간선으로 이루어진 그래프가 주어진다. 임의의 두 역 사이에 경로가 항상 존재할 때, 각 노드로부터 사이클 형상 까지의 거리를 구해보자.

제한 TL : $2$ sec, ML : $512$ MB $3 ≤ N ≤ 3,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs) 풀이 $N$개의 간선으로 이루어진 그래프에서 사이클을 떼네어볼 수 있는가를 묻는 교육적인 문제이다. 나는 개인적으로 indegree를 이용한 bfs를 이용해 사이클을 분리하는 방식을 선호한다.

다음의 과정을 보자. 간선 정보를 입력 받으면서 indegree를 카운트 해주면.....