공중도시

• 최소 갯수의 엣지를 추가해서 그래프를 2-edge-connected 로 만드는 방법을 물어보는 문제.
• Kingpin Escape를 트리가 아닌 일반 그래프로 확장한 문제이다. 그래프를 처음에 BECC들로 분할해서 bridge tree로 변환하고 나면, 나머지는 동일하게 풀수 있다. 그래프 전체를 BECC로 만드는 방법 을 참고.
• 시간복잡도는 O(V+E).
• 다만, 파이썬으로는 시간이 좀 빡빡할수 있다. bridge tree를 만들때, 단절선을 먼저 구해놓고, 단절선들을 제거한뒤에 다시 그래프에서 커넥티드 컴포넌트들을 찾는 2 path 방식으로 BECC들을 뽑아내다가 시간 초과를 겪었다. 한번의 DFS로 BECC 추출까지 하는 방식으로 코드를 개선해서 (현재 teflib에 구현되어있는 방식) 통과했다.
• 그리고 또 한가지 실수하기 쉬운 부분은, 주어지는 그래프가 중복 엣지를 포함할수도 있기 때문에, 단절선을 구할때 그 점을 신경써야 한다는 것.

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

• Dependency
  • teflib.graph.bridge_graph
  • teflib.graph.dfs