27071번 - 크루스칼 알고리즘

정휘는 알고리즘 강의에서 그래프의 최소 신장 트리를 구하는 알고리즘인 크루스칼 알고리즘에 대해 배웠다. 크루스칼 알고리즘은 다음과 같이 동작한다.

1. 간선을 가중치 오름차순으로 정렬한다. 이때 두 간선의 가중치가 동일하다면 두 간선 중 어떠한 것이 앞에 와도 상관없다.
2. 최소 신장 트리를 이루는 간선의 집합 $F$를 공집합으로 초기화한다. ($F := \varnothing$)
3. 간선을 차례대로 보면서, 만약 간선 $e$의 양 끝점이 $F$의 간선들을 통해 연결되어 있지 않다면 $e$를 $F$에 추가한다. 즉, $F \cup \{e\}$에 사이클이 없다면 $F$에 $e$를 추가한다.

연결 무향 가중치 그래프가 주어졌을 때 알고리즘이 최소 신장 트리를 구한다는 것은 어렵지 않게 증명할 수 있다.

정휘는 (1)에서 가중치가 같은 간선을 정렬하는 기준이 없다는 점이 마음에 들지 않는다. 같은 그래프가 주어져도 다른 결과가 나올 수 있다는 것은 용납할 수 없는 일이다. 정휘는 자신의 분노를 수치화하기 위해 얼마나 다양한 결과가 나올 수 있을지 계산하려고 했지만, 알고리즘 강의가 끝날 때까지 그 방법을 찾지 못해서 여러분에게 문제로 내기로 했다.

$N$개의 정점과 $M$개의 간선으로 구성된 단순 연결 무향 가중치 그래프가 주어진다. 크루스칼 알고리즘을 이용해 최소 신장 트리를 구할 때, $F$에 간선을 추가하는 방법의 수를 구하는 프로그램을 작성해 보자. $F$에 추가된 간선들의 집합이 다르거나, 간선들을 추가하는 순서가 다르다면 다른 방법으로 센다.

첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐 두 간선이 연결하는 정점 번호 $u_i, v_i$와 간선의 가중치 $w_i$가 주어진다.

$F$에 간선을 추가하는 순서로 가능한 경우의 수를 $998\,244\,353(= 119 \times 2^{23} + 1)$으로 나눈 나머지를 출력한다.

• $2 \leq N \leq 400$
• $N-1 \leq M \leq N(N-1)/2$
• $1 \leq u_i < v_i \leq N$
• $1 \leq w_i \leq 10^9$
• $i \neq j$ 이면 $(u_i, v_i) \neq (u_j, v_j)$
• 모든 정점은 간선을 통해 서로 직/간접적으로 연결되어 있다.