무방향그래프에서의 Cut Vertex와 Biconnected Components

우리는 종종 Connected Component에 대해 들어보곤 한다.

주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포함해야하며, 하나라도 더 추가한 순간 disconnected해야한다)를 의미한다.

여기에서 사이클에 대한 조건을 추가한 개념이 Biconnected Component(BCC)라고 할 수 있다.

 

위의 그림과 같은 무방향 간선 (연결) 그래프가 있다고 가정하자.

이 상태에서 vertex A 및 A와 연결된 모든 edge를 삭제하면 그래프는 (D,G,H)와 (B,C,E,F,I,J)로 분리된 disconnected graph가 된다.

이렇게 해당 그래프에서 어떤 vertex v와, v와 연결된(incident) 모든 edge를 제거했을 때 그래프가 disconnected 된다면 vertex v를 그래프의 Cut Vertex(articulation point)라고 한다. 

 

어떤 그래프가 Biconnected하다는 것은, 1️⃣ Connected Graph이면서 2️⃣ Cut Vertex가 없다는 것을 의미한다.

그리고 Connected Component와 유사하게, 해당 그래프의 maximal biconnected subgraph의 집합을 Biconnected Components라고 한다.

이 때, BCC에서 특정 vertex를 삭제하더라도 connected 성질은 유지된다.

또한 edge e1과 e2가 같은 BCC에 속해있다면, e1과 e2를 포함하는 cycle은 무조건 같은 BCC 안에 속하게 된다.

즉 하나의 Biconnected Component는 사이클의 집합이고, 이를 하나의 정점으로 대체하면 트리를 얻어낼 수 있다(해당 예시는 하나의 vertex가 두 개의 BCC에 속해있기 때문에 partitioning하기 어렵다).

 

Biconnected Component와 Cut Vertex는 DFS 알고리즘(DFS Tree)을 통해 구할 수 있다.

(이 때, DFS Tree는 pre라는 list는 사용해서 vertex의 방문 순서를 기록, low라는 list를 사용해야 한다.)

low(v) : v의 어떤 descendant(자손 노드) u와 incident한 back edge(u,w)가 있을 때, low(v) = min( pre(v), pre(w) )

수식으로 쓰면 복잡하지만, 결국 내 descendant node가 ancestor node로의 back edge를 가지고 있는지 체크하기 위한 list라고 보면 된다.

 

Cut Vertex 구하기

1️⃣ DFS Tree의 root node의 child가 두 개 이상이라면, root node는 Cut Vertex이다.

: 각 child끼리는 root node 없이는 reachable하지 않기 때문에 root node를 삭제하면 disconnected하다.

2️⃣ non-root node v의 child node s가 s의 descendant에서 v의 proper ancestor(v를 미포함한 조상 노드) back edge를 가지고 있지 않다면 v는 Cut Vertex이다.

: v를 제거할 경우, v의 child인 s를 포함한 subtree의 어떤 node도 v의 proper ancestor에 reachable하지 않다. 따라서 v를 제거하면 disconnected가 된다.

3️⃣ leaf node는 Cut Vertex가 아니다.

: leaf node는 child가 없기 때문에 leaf node를 삭제해도 graph는 언제나 connected하다.

이러한 성질을 이용해서 DFS를 수행하면서 모든 cut vertex를 구할 수 있다.

root node의 경우에는 child가 2개 이상인지 체크하고, non-root node일 경우 dfs에서 low 값을 계속 업데이트 한다. child에 대한 dfs가 끝났을 경우 pre(v)와 low(u)를 비교해서 low(u) >= pre(v)일 경우 v는 cut vertex이다.

(u에서 reachable한 최소 pre값을 가진 node가 v보다 나중에 방문된다는 것은, proper ancestor로의 path가 없다는 것)

 

아래는 Cut Vertex를 C++로 구현한 코드이다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int V, E, cnt, pre[10005], low[10005];
vector<int> graph[10005], cutVertex;
bool visit[10005];

void dfs(int v, int p) {
	visit[v] = true;
	pre[v] = low[v] = ++cnt;
	int children = 0, isCutVertex = 0;

	for (auto u : graph[v]) {
		if (u == p)continue;
		if (visit[u]) {
			low[v] = min(low[v], pre[u]);
		}
		else {
			dfs(u, v);
			low[v] = min(low[v], low[u]);
			if (p && low[u] >= pre[v])
				isCutVertex = 1;
			++children;
		}
	}
	if (p == 0 && children > 1)
		isCutVertex = 1;
	if (isCutVertex)
		cutVertex.push_back(v);
}

int main() {
	scanf("%d%d", &V, &E);

	for (int i = 0, u, v; i < E; i++) {
		scanf("%d%d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= V; i++) {
		if (!visit[i])
			dfs(i, 0);
	}

	sort(cutVertex.begin(), cutVertex.end());

	printf("%d\n", cutVertex.size());
	for (int v : cutVertex)
		printf("%d ", v);
	return 0;
}

time complexity: O(n+m)

 

Biconnected Component 구하기

Biconnected Component는 cut vertex를 찾는 연산에 stack을 추가로 이용해서 구할 수 있다.

(BCC가 edge를 partitioning하기 때문에 특정 BCC에 속하는 edge set을 return하도록 구현했다)

 

1️⃣ vertex v와 incident한 vertex u에 대해 edge(v, u)를 check할 때 마다 해당 edge를 stack에 push한다.

2️⃣ 만약 v의 explore 도중 u에 의해 v가 cut vertex임이 밝혀지거나( low(u) >= pre(v) ), root node에 대한 explore가 끝나면 edge(u, v)가 나올 때 까지 stack 상의 모든 edge를 pop하며 이것이 하나의 biconnected component에 속한 edge set이 된다.

 

마찬가지로 BCC를 C++로 구현한 코드이다.

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

int V, E, cnt, pre[10005], low[10005];
vector<int> graph[10005], cutVertex;
vector<vector<pair<int, int>>> bcc;
bool visit[10005];
stack<pair<int, int>> s;

void dfs(int v, int p) {
	visit[v] = true;

	pre[v] = low[v] = ++cnt;

	for (int u : graph[v]) {
		if (u == p)continue;
		if (pre[v] > pre[u])s.push(make_pair(v, u));
		if (visit[u]) {
			low[v] = min(low[v], pre[u]);
		}
		else {
			dfs(u, v);

			low[v] = min(low[v], low[u]);

			if (low[u] >= pre[v]) {
				bcc.emplace_back();

				while (true) {
					pair<int, int> edge = s.top(); s.pop();
					bcc.back().push_back(edge);

					if (edge == pair<int, int>(v, u))break;
				}
			}
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	scanf("%d%d", &V, &E);

	for (int i = 0, u, v; i < E; i++) {
		scanf("%d%d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for (int i = 1; i <= V; i++) {
		if (!visit[i])
			dfs(i, 0);
	}

	for (auto x : bcc) {
		for (auto k : x) {
			printf("%d %d\n", k.first, k.second);
		}
		printf("\n");
	}
	return 0;
}

time complexity: O(n+m)