Cut Vertex
- 어떤 한 노드 s를 지우면 Disconnected Graph가 되는 것
- x노드와 y노드를 지나가는 모든 Path가 s노드를 지나가는 것
(s를 지나가는 방법 말고는 다른 경로가 없음)
아이디어 1.
모든 노드에 대하여,
하나씩 지워보고 Connected Component를 돌리는 방법이 있고, 이 경우 시간복잡도는 O(nm)이다.
Connected Component를 돌리기 위해서는 dfs를 하고 그 dfs는 n+m 이 걸린다.
따라서 사실 상 n * (n+m)인데 m을 가져와서 O(nm)으로 표기한 것이다.
아이디어 2.
- DFS를 돌려서 DFS Tree를 만든다.
- DFS Tree의 Root는 자식 노드가 2개 이상이면 Cut vertex이다.
- 모든 노드에 대하여 해당 노드를 Root로 하는 DFS Tree를 만든 다음, 자식 노드가 2개 이상인지 검사한다.
- 이 경우에도 O(nm)이 걸린다.
DFS를 한 번만 돌려서는 root만 명확하게 Cut vertex인지 알 수 있기 때문이다.
그런데 DFS 한 번 돌려서 모든 노드에 대해 Cut vertex인지 판단하는 방법이 있다.
로직
1) DFS 돌린다.
- DFS Tree의 Root는 자식 노드가 1개보다 크면 Cut vertex이다.
- Root가 아닌 노드 t에 대하여 다음을 진행한다.
2) 각 노드 t에 대해 l(t)를 계산한다.
- Pre(t)의 최소값
- Back Edge를 타고 올라갈 수 있는 제일 높은 층수
- l(t)는 Child들의 l값인 l(u) 중에서 최소값
만약 pre(t) <= l(u) 이면 t는 cut vertex
즉, 자식들이 갈 수 있는 가장 위의 층이 나의 층수보다 크거나 같으면 내가 cut vertex이다.
child들이 나를 통해서만 위쪽으로 올라갈 수 있다는 의미가 되기 때문이다.
Biconnected Component(BCC)
- 어떤 노드 쌍에 대해서도 2개의 Path가 있다는 것을 의미
BCC이면 그래프에 Cut vertex가 없다.
2개의 Path가 있기 때문에, 어떤 엣지를 죽여도 서로 연결되어 있기 때문이다.
반대로도 그래프에 Cut vertex가 없으면 Biconnected 이다.
따라서 BCC를 Detect하기 위해서는 Cut vertex를 찾아서 할 수 있다.
Game Programmer