====== 공중도시 ======

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

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

  * Dependency
    * [[:ps:teflib:graph#bridge_graph|teflib.graph.bridge_graph]]
    * [[:ps:teflib:graph#dfs|teflib.graph.dfs]]

{{tag>BOJ ps:problems:boj:다이아몬드_4}}