ps:problems:boj:10806
공중도시
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 10806 |
| 문제명 | 공중도시 |
| 레벨 | 다이아몬드 4 |
| 분류 |
BCC |
| 시간복잡도 | O(V+E) |
| 인풋사이즈 | V<=100,000, E<=200,000 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 81860KB / 956ms |
| 최고기록 | 956ms |
| 해결날짜 | 2023/03/13 |
풀이
- 최소 갯수의 엣지를 추가해서 그래프를 2-edge-connected 로 만드는 방법을 물어보는 문제.
- Kingpin Escape를 트리가 아닌 일반 그래프로 확장한 문제이다. 그래프를 처음에 BECC들로 분할해서 bridge tree로 변환하고 나면, 나머지는 동일하게 풀수 있다. 그래프 전체를 BECC로 만드는 방법 을 참고.
- 시간복잡도는 O(V+E).
- 다만, 파이썬으로는 시간이 좀 빡빡할수 있다. bridge tree를 만들때, 단절선을 먼저 구해놓고, 단절선들을 제거한뒤에 다시 그래프에서 커넥티드 컴포넌트들을 찾는 2 path 방식으로 BECC들을 뽑아내다가 시간 초과를 겪었다. 한번의 DFS로 BECC 추출까지 하는 방식으로 코드를 개선해서 (현재 teflib에 구현되어있는 방식) 통과했다.
- 그리고 또 한가지 실수하기 쉬운 부분은, 주어지는 그래프가 중복 엣지를 포함할수도 있기 때문에, 단절선을 구할때 그 점을 신경써야 한다는 것.
코드
(다이아몬드 이상은 코드 생략)
- Dependency
ps/problems/boj/10806.txt · 마지막으로 수정됨: 2023/03/13 02:40 저자 teferi
토론