https://www.acmicpc.net/problem/27877 27877번: 제곱수 덱 2 $x$의 최솟값을 $998\,244\,353$로 나눈 나머지를 출력한다. 만약 $N$장의 카드를 하나의 덱으로 합칠 수 없다면 -1을 출력한다. www.acmicpc.net 문제가 상당히 간단하다. 관점을 조금 바꿔보자. 각 카드를 정점으로, 덱을 컴포넌트로 보면, 이 문제는 MST 문제로 환원될 수 있다. 가중치 간선의 곱에 대한 MST인데, 결과에 log를 씌운다 하면, 결국 곱셈이 덧셈으로 바뀌기에, 일반적인 MST 문제와 같다. 크루스칼 알고리즘을 생각해보자. 가중치가 적은 간선부터 선택하며 만약 그 가중치를 선택할 때 사이클이 생긴다면 선택하지 않는 식으로 작동하는 알고리즘이다. 예제어서 주어진 14..
