백준 4792 레드 블루 스패닝 트리

https://www.acmicpc.net/problem/4792

4792번: 레드 블루 스패닝 트리

크루스칼과 비슷한 방식으로 스패닝 트리를 따질 것이다. 분리집합을 두 개 생각해 보자. 

먼저 첫번째 유니언 파인드는 빨간 간선을 모두 사용하여 돌린 후 하나의 집합을 만들기 위해 최소 몇개의 파란 간선이 필요한지 확인한다. (아예 스패닝 트리를 만드는게 불가능할수도 있기에 확인해 주자.)

2번째 유니언파인드는 파란 간선만 사용하면서 진행하여 스패닝 트리에 최대 몇개의 파란 간선이 존재할 수 있을지 따져 준다.

푸른 간선의 최소와 최대 사이에 있는 모든 수는 간선을 적절히 선택하여 만들어짐을 생각해볼 수 있기에, k가 범위에 들어오는지만 따져주면 된다. (첫번째 유니언 파인드로 만든 스패닝 트리에 파란 간선을 하나씩 추가하면서 연결성이 유지되게 빨간 간선을 삭제할 수 있다. 이게 불가능할 경우 2번째 유니언파인드에서 체크되기 때문이다)