Graph - BCC

Biconnected Component (BCC)

• 분리를 해가지고 싸이클이 있는 컴포넌트를 최대한 만들기.
• 노드 1개 짜리 컴포넌트의 경우도 BCC라고 본다.
• 분리의 기준(자르는 기준) : Cut Vertex
  단 삭제되는 것이 아닌, 각 컴포넌트에 복사되어 들어감.
  (Cut vertex는 분리의 기준이자 컴포넌트의 일부)

---

알고리즘

1. DFS를 통해 cut vertex를 찾는다.
이때 노드가 cut vertex가 아니면 할 일이 없으므로 다음 노드로 이동한다.

2. 루트가 cut vertex 라면
루트와 연결된 child들은 서로 분리된 컴포넌트이다.
따라서 루트를 복사해서 분리된 컴포넌트로 만들어 준다.
이제 분리된 컴포넌트들에서 각자 BCC를 계속 찾으면 된다.

3. 루트가 아닌 노드 i에 대하여
i 가 컴포넌트 내의 cut vertex 라면
그 노드 i를 cut vertex로 만드는 child v와 cut vertex 로 만들지 않는 x가 있다.
루트에서 분리했던 것 처럼 노드 i를 복사하여 각각 x와 v로 분리된(포함된) 컴포넌트로 만들어 준다.

이때 x의 경우 노드 i가 cut vertex가 아니었기 때문에 노드 i의 부모는 i와 분리되지 않고 연결된 상태로 냅둔다.
(cut vertex 가 아니라는 소리는 x에서 i의 부모로 갈 수 있는 back edge가 있다는 의미이다.
따라서 x, i, 부모 모두 컴포넌트안에 포함된다.)

v의 경우 노드 i가 cut vertex 이므로 노드 i는 i의 부모와 분리된다.
(노드 i가 cut vertex 라는 말은 더 이상 i의 부모로 갈 수 있는 back edge 가 없다는 말이다.
따라서 노드 i와 i의 부모는 같은 컴포넌트가 될 수 없다. 싸이클이 아니기 때문이다.)

4. child v에서 노드 i로 갈 수있는 길이 back edge에 있다면
싸이클을 형성하므로 v와 i는 같은 컴포넌트에 포함된다.

그러나 child v에서 노드 i로 갈 수 있는길이 back edge에 없다면
싸이클을 형성하지 못하므로 v 와 i는 또다시 분리된다.
그렇게 분리되면 노드 i의 컴포넌트에는 노드 i 홀로 존재하게 되는데
이런 노드 1개 짜리 컴포넌트의 경우에도 BCC라고 본다.