Biconnected Component

글을 읽기 전에 SCC와 절점 절선 개념을 배우고 오길 추천함.

간단히 요약하자면 그래프에서 사이클 비슷한 건 정점 하나로 묶어버리고 트리라 치는 알고리즘이다.

이러한 점에서는 SCC랑 엄청 비슷하다. 실제로 SCC의 무향 버전이라고 생각해도 좋음. SCC는 사이클을 정점 하나라고 묶어버리고 DAG로 만드는 방법이면 BCC는 사이클을 간선 하나라고 묶어버리고 트리로 만드는 방법이다. 결국은 다 사이클이 싫어서 하는 짓임. 사용 용도도 SCC랑 상당히 비슷하다.

BCC에는 두가지 종류가 있다. SCC는 하나만 있는데 얘는 좀 다르다.

 * Vertex-disjoint biconnected component : 그래프에서 절점을 제거함으로써, 컴포넌트를 나눔

 * Edge-disjoint biconnected component : 그래프에서 절선을 제거함으로써, 컴포넌트를 나눔

일반적으로 사람들이 BCC라고 하는 건 전자에 속한다.

전자의 BCC는, 간선이 주가 되는 컴포넌트이다. 즉 컴포넌트가 정점의 집합이 아니라 간선의 집합이다. (사실 컴포넌트라는 건 간선 + 정점의 집합이라서, 정점의 집합이 아니라는 건 실제로는 의미 없는 말이다. 그냥 graphical하게 설명하기 위함으로 알아두길...) 그래서 그러한 BCC로 분리를 하면, 간선들의 집합으로 이쁘게 떼어지는 걸 아래에 있는 사진만 봐도 잘 알수 있을 것이다.

한편, 후자의 BCC는 SCC와 비슷하게 컴포넌트가 정점의 집합으로 구성된다. 조금 더 익숙한 형태이고 난이도도 조금 더 쉬움.

BCC를 구분하는 건 꽤 쉬운 편이다. (..사실 어려운데 내가 쉬운 구현을 들고 왔다. 나도 인터넷에서 본 구현인데 이거 말고는 다 잘 이해가 안간다.)

 * Edge-disjoint 버전은, 말그대로 절선을 떼내고 flood fill을 돌리면 된다. 개념상 이렇겐 하지만 실제 이렇게 하기는 귀찮으니 아래 구현을 응용함.

 * Vertex-disjoint 버전은 tricky하지만 상당히 상당히 깔끔하다. 뭐라 그래야지 총을 쏜다 (?) 라는 식으로 생각하면 좋다. 먼저 lowlink를 다 구해놓고, 같은 BCC를 color로 묶어서 생각하자. 절선의 상황이 오면 그때 새로운 color를 만들어 준 후, 자기 노드에 그 color를 덧씌워주고 (사진처럼). 서브트리에 color를 칠해주며 dfs를 돌면 된다.

모두 O(n+m)에 작동한다.

https://gist.github.com/koosaga/6f6fd50dd7067901f1b1

연습 문제 : http://59.23.113.171/pool/starship_please/starship_please.php?pname=starship_please (더블릿이다.)