ps:problems:boj:17098
목차
Boomerangs
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 17098 |
| 문제명 | Boomerangs |
| 레벨 | 다이아몬드 4 |
| 분류 |
BCC |
| 시간복잡도 | O(V+E) |
| 인풋사이즈 | V<=5*10^5, E<=5*10^5 |
| 사용한 언어 | PyPy |
| 제출기록 | 321080KB / 1652ms |
| 최고기록 | 1652ms |
| 해결날짜 | 2024/01/20 |
풀이
- 연결된 엣지쌍들 ((u-v), (v-w)) 중에서 그 엣지 두개를 제거했을때 그래프를 분리시킬 수 있는 것의 갯수를 구하라는 문제.
- 일단 엣지 하나가 단절선이라면 당연히 가능하다. 단절선에 해당하는 엣지 하나만 제거해도 그래프가 분리되기 때문이다. 이것을 세는것은, 각 단절선마다 단절선에 연결된 엣지의 수를 모두 더해준 다음에, 중복으로 카운트 된 단절선 두개가 붙어있는 쌍의 갯수를 빼주면 된다.
- 엣지가 둘다 단절선이 아니지만 조건을 만족시키는 경우는, u-v-w 모양의 부메랑을 제거했더니 v가 u와 w를 포함하는 컴포넌트로부터 분리되는 경우이다. 이것이 되는 조건은, u,v,w가 모두 같은 BCC 안에 있고, v는 u와 w외에 그 BCC 안에서 연결된 노드가 없어야 한다. 다른 BCC에 연결된 노드는 있어도 된다는 점에 주의하자. 이것때문에 단순히 전체 그래프안에서의 차수를 확인해서는 안되고, BCC단위로 분리된 그래프에서 차수를 다시 계산해줘야 한다.
- 이 두 경우에 해당하는 엣지쌍의 갯수를 각각 구해서 더해주면 된다. 실제 필요한 작업은 엣지단위로 BCC를 분리하고, 각 BCC에서 차수를 찾고, 단절선을 구하고, 단절선끼리 연결된 페어의 갯수를 찾는 정도의 작업들이 필요하지만, BCC를 O(V+E)에 분리해놓고 나면 나머지 작업들은 간단하게 처리된다.
- BCC에서 접근하지 않고, 그냥 dfs spanning tree의 구조에서 백엣지의 갯수와 등등을 이용해서 조건을 정리하고 그것을 기준으로 계산할 수도 있겠지만, 결국은 비슷한 원리이므로 이해가 편한식으로 추상화시키면 될듯 하다.
코드
- 다이아몬드 이상은 코드 생략
- Dependency: teflib.graph.BiconnectedComponent
ps/problems/boj/17098.txt · 마지막으로 수정됨: 2024/01/22 14:33 저자 teferi
토론