35509번 - Good Bye, 최소 스패닝 트리! 스페셜 저지

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

$N$개의 정점과 $M$개의 간선으로 이루어진 가중치 있는 무방향 그래프가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 붙어 있고, 간선은 $1$번부터 $M$번까지 번호가 붙어 있다.

그래프의 최소 스패닝 트리(MST)는 다음과 같이 정의된다.

• 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 간선 가중치의 합이 최소인 트리

그래프의 최소 병목 스패닝 트리(MBST)는 다음과 같이 정의된다.

• 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중에서 간선 가중치의 최댓값이 최소인 트리

입력으로 주어진 그래프에 대해서, MST이면서 MBST가 아닌 것과, MBST이면서 MST가 아닌 것을 각각 찾아라.

첫째 줄에 정수 $N,M$이 공백으로 구분되어 주어진다.

다음 $M$개의 줄에 그래프의 간선을 나타내는 정수 $u_i,v_i,w_i$가 공백으로 구분되어 주어진다. $i$번 간선이 정점 $u_i$와 $v_i$를 $w_i$의 가중치로 이음을 나타낸다.

주어진 그래프는 연결 그래프임이 보장된다.

첫째 줄에 MST이면서 MBST가 아닌 것이 있으면 YES, 없으면 NO를 출력한다.

YES를 출력한 경우 다음 $N-1$개의 줄에 MST를 이루는 간선의 번호를 출력한다.

다음 줄에 MBST이면서 MST가 아닌 것이 있으면 YES, 없으면 NO를 출력한다.

YES를 출력한 경우 다음 $N-1$개의 줄에 MBST를 이루는 간선의 번호를 출력한다.

만약 정답이 여러 가지인 경우, 아무거나 하나 출력한다.

• $2\le N\le 100\,000$
• $N-1\le M\le 300\,000$
• $1\le u_i,v_i\le N$ ($1 \le i \le M$)
• $u_i\ne v_i$ ($1 \le i \le M$)
• $1\le w_i\le 10^9$ ($1 \le i \le M$)
• 주어진 그래프는 연결 그래프이다.
• 서로 다른 두 정점 사이에 간선이 여러 개 존재할 수 있음에 유의하라.