위상 정렬 경우의 수
골드 I의견: 0
방향 비순환 그래프(DAG)가 주어진다. 이 그래프는 포레스트 구조로, 각 노드의 진입 차수(in-degree)는 최대 \(1\)이다.
이 그래프의 서로 다른 위상 정렬 순서의 수를 \((10^9 + 7)\)로 나눈 나머지를 구하여라.
위상 정렬 순서란, 모든 간선 \((u, v)\)에 대해 노드 \(u\)가 노드 \(v\)보다 앞에 오는 노드의 순열이다.
- \(1 \le N \le 150\,000\)
- \(0 \le M \le N - 1\)
- 주어진 그래프는 포레스트 형태의 DAG이다 (각 노드의 진입 차수 \(\le 1\), 사이클 없음).
- \(1 \le u, v \le N\), \(u \ne v\)
첫째 줄에 노드의 수 \(N\)과 간선의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 간선 \(u\), \(v\)가 공백으로 구분되어 주어진다 (\(u \to v\) 방향).
서로 다른 위상 정렬 순서의 수를 \((10^9 + 7)\)로 나눈 나머지를 출력한다.
3 2
1 2
2 3
1
\(1 \to 2 \to 3\)으로 순서가 고정되어 있으므로 유효한 위상 정렬은 단 \(1\)가지이다.
3 0
6
선후 관계가 없으므로 \(3\)개의 노드를 임의의 순서로 나열해도 된다. \(3! = 6\)가지이다.
3 2
1 2
1 3
2
\(1\)이 가장 먼저, \(2\)와 \(3\)은 순서를 바꿔도 되므로 \((1,2,3)\)과 \((1,3,2)\)로 총 \(2\)가지이다.
riseoj 작성
출처 Original
평가 및 의견
위상 정렬 경우의 수
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
위상 정렬 경우의 수