그래프의 싱크

시간 제한1초메모리 제한128 MB

요약
방향 그래프가 주어질 때, v에서 도달 가능한 모든 노드가 다시 v로 돌아올 수 있는 노드 v를 모두 찾아 오름차순으로 출력한다.
난이도

보통10점 중 7점

유형
그래프, DFS, 구현, 정렬
정답자
아직 제출이 없습니다

문제

방향 그래프 G=(V,E)G = (V, E)가 주어진다.

임의의 두 노드 u,v∈Vu, v \in V에 대해, EE에 속한 간선만을 이용해 uu에서 vv로 가는 경로가 존재하면 이를 u→vu \to v로 표기한다.

노드 v∈Vv \in V가 자신에서 도달할 수 있는 모든 노드로부터 다시 vv로 돌아오는 경로를 가진다면, 즉 다음 조건을 만족하면 vv를 싱크(sink) 라고 부른다.

∀w∈V, (v→w)  ⟹  (w→v)\forall w \in V,\ (v \to w) \implies (w \to v)

그래프 GG의 모든 싱크를 모은 집합을 bottom(G)\mathrm{bottom}(G)로 표기한다.

bottom(G)={ v∈V:∀w∈V, (v→w)  ⟹  (w→v) }\mathrm{bottom}(G) = \{\, v \in V : \forall w \in V,\ (v \to w) \implies (w \to v) \,\}

주어진 그래프 G=(V,E)G = (V, E)에 대해 bottom(G)\mathrm{bottom}(G)를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 노드의 수 nn (1≤n≤5 0001 \le n \le 5\,000)과 음이 아닌 정수 mm (0≤m≤100 0000 \le m \le 100\,000)이 주어진다. 이는 V={1,2,…,n}V = \{1, 2, \dots, n\}이고 간선의 수가 ∣E∣=m|E| = m임을 뜻한다.

이어서 각 간선을 나타내는 mm개의 정수 쌍 v1 w1 v2 w2 … vm wmv_1\ w_1\ v_2\ w_2\ \dots\ v_m\ w_m이 공백으로 구분되어 주어진다. 각 쌍 (vi,wi)(v_i, w_i)는 간선 (vi,wi)∈E(v_i, w_i) \in E를 의미하며, 이 정수들은 여러 줄에 걸쳐 나타날 수 있다.

nn이 00인 값이 주어지면 입력이 끝난 것이며, 이 경우는 처리하지 않고 프로그램을 종료해야 한다.

출력

각 테스트 케이스마다 bottom(G)\mathrm{bottom}(G)에 속한 모든 노드를 한 줄에 출력한다. 노드는 오름차순으로 정렬하고 공백으로 구분한다. 만약 bottom(G)\mathrm{bottom}(G)가 공집합이면 빈 줄을 출력한다.

예제2

  1. 예제 1

    입력
    3 3
1 3 2 3 3 1
2 1
1 2
0
    예상 출력
    1 3
2

  2. 예제 2

    입력
    2 1
2 1
2 0

5 5
1 2 2 3 3 1 5 4 4 3
5 5
1 2 2 3 3 1 3 4 4 5
5 1
5 1
5 6
1 2 2 3 3 1 3 4 4 5 5 3
0
    예상 출력
    1
1 2
1 2 3
5
1 2 3 4
1 2 3 4 5