토너먼트 도달 가능성
골드 II의견: 0
토너먼트 그래프는 \(N\)개의 팀과 \(M\)개의 단방향 진출 경로로 구성된 비순환 방향 그래프(DAG)이다. 간선 \(u \to v\)는 팀 \(u\)가 이긴 후 팀 \(v\)의 경기로 진출할 수 있음을 나타낸다.
각 팀 \(u\)에 대해, \(u\)에서 출발해 도달할 수 있는 팀의 수 (자기 자신 포함)를 구하여라.
- \(1 \le N \le 2\,000\)
- \(0 \le M \le N(N-1)/2\)
- 모든 간선 \(u \to v\)에서 \(u < v\) (사이클 없음 보장)
첫째 줄에 팀의 수 \(N\)과 진출 경로 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 방향 간선 \(u\), \(v\)가 공백으로 구분되어 주어진다. (\(u < v\)가 보장된다.)
각 팀 \(1\), \(2\), \(\dots\), \(N\)에 대해 도달 가능한 팀의 수를 공백으로 구분해 한 줄에 출력한다.
5 5
1 2
1 3
2 4
3 4
4 5
5 3 3 2 1
노드 \(1\): \(1,2,3,4,5\)에 모두 도달 → \(5\). 노드 \(2\): \(2,3,4,5\) → \(4\). 노드 \(3\): \(3,4,5\) → \(3\). 노드 \(4\): \(4,5\) → \(2\). 노드 \(5\): \(5\)만 → \(1\).
4 4
1 2
1 3
1 4
2 4
4 2 1 1
노드 \(1\): \(1,2,3,4\) → \(4\). 노드 \(2\): \(2,4\) → \(2\). 노드 \(3\): \(3\) → \(1\). 노드 \(4\): \(4\) → \(1\).
riseoj 작성
출처 Original
평가 및 의견
토너먼트 도달 가능성
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
토너먼트 도달 가능성