R01408
마법 수로 판별
골드 IV레이팅
의견: 0
설명
마법사 왕국의 \(N\)개 도시를 잇는 후보 도로 \(M\)개가 주어진다. 이 그래프에서 최소 신장 트리(MST)는 여러 개 존재할 수 있다.
각 도로를 다음 세 가지로 분류하여라.
- 필수(essential): 모든 MST에 반드시 포함되는 도로
- 선택적(optional): 어떤 MST에는 포함되지만 모든 MST에 포함되지는 않는 도로
- 불필요(useless): 어떤 MST에도 포함되지 않는 도로
그래프가 연결되어 있음이 보장된다.
제약
- \(2 \le N \le 200\,000\)
- \(N-1 \le M \le 300\,000\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
- 같은 두 도시를 잇는 도로는 최대 한 개이다.
- 그래프는 연결되어 있다.
입력 형식
첫째 줄에 도시의 수 \(N\)과 도로의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 걸쳐 도로 양 끝 도시 번호 \(u\), \(v\)와 비용 \(w\)가 공백으로 구분되어 주어진다.
출력 형식
\(M\)개의 줄에 걸쳐, \(i\)번째 도로의 분류를 입력 순서대로 출력한다. 필수 도로면 essential, 선택적 도로면 optional, 불필요한 도로면 useless를 출력한다.
예제 1
입력
4 5
1 2 1
2 3 2
3 4 2
2 4 2
1 3 5
출력
essential
optional
optional
optional
useless
설명
비용 \(1\)인 간선 (1번-2번)은 모든 MST에 반드시 포함되어 필수이다. 비용 \(2\)인 세 간선은 그 중 어느 둘을 선택해도 MST가 되므로 모두 선택적이다. 비용 \(5\)인 간선은 어떤 MST에도 포함되지 않으므로 불필요하다.
예제 2
입력
3 2
1 2 3
2 3 7
출력
essential
essential
설명
\(N=3\)이고 간선이 2개뿐이므로 유일한 신장 트리는 두 간선을 모두 포함한다. 따라서 두 간선 모두 필수이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
마법 수로 판별
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 수로 판별
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기