사용자 도구

사이트 도구


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에 구현되어있는 방식) 통과했다.
  • 그리고 또 한가지 실수하기 쉬운 부분은, 주어지는 그래프가 중복 엣지를 포함할수도 있기 때문에, 단절선을 구할때 그 점을 신경써야 한다는 것.

코드

(다이아몬드 이상은 코드 생략)

토론

댓글을 입력하세요:
E V K T W
 
ps/problems/boj/10806.txt · 마지막으로 수정됨: 2023/03/13 02:40 저자 teferi