Cut vertex, cut edge(절단점, 절단선-bridge)

해당 게시글은 아래 속성에 맞춰 작성되어있습니다 :)

* 무향 그래프(양방향 그래프, Undirected graph)

* Cut vertex(절단점, 단절점)

  절단점이란 이 점과 이어진 모든 간선을 지웠을 때 두 개 이상의 Component로 나뉘어 지는 정점을 말한다.

  역방향 간선을 이용하여 DFS 한 번만에 절단점을 찾을 수 있다.

  DFS를 통해 DFS spanning tree를 구성하면 정점 u는 아래처럼 분류할 수 있다.

1. u가 root다

2. u가 root가 아니다.

1. u가 root다

  정점 u가 root인 경우, 자식의 개수에 따라 절단점이 될 수도 있고 아닐 수도 있다.

  자식이 없는 경우는 당연하고, 하나인 경우에도 root가 사라진다고 두 개의 Component로 나눠지는 것은 아니기 때문에 자식의 개수가 2개 이상인 경우에만 절단점이 될 수 있다.

2. u가 root가 아니다.

  u가 root가 아닌 경우, DFS spanning tree 상에서 자식이 현재 정점 u보다 위로 올라갈 수 있는지(사이클이 존재하는지) 판단하면 된다. 이는 곧 역방향 간선이 u의 선조로 올라갈 때와 동치가 된다. 중요한 사실은 자식 중에 u로 올라오는 역방향 간선이 있어도 된다는 점이다. 해당 역방향을 추적기 위해 방문하는 정점에 언제 방문을 했는지를 체크하는 배열을  기존 방문 여부를 확인하는 visited 배열을 변형한다. 보통 구현할 때, 일찍 방문한 정점은 숫자가 낮게 설정한다.

  코드에서는 이를 discovered로 구현했으며, subTree가 해당 자식트리가 갈 수 있는 가장 작은 번호(연결된 정점 중 가장 일찍 발견한 정점)을 반환하게 설정하였다. 

- 코드

vector<vector<int>> adj;
vector<int> discovered;
vector<bool> isCutVertex;
int counter;
int findCutVertex(int here, bool isRoot) {
	discovered[here] = counter++;
	int ret = discovered[here];
	int children = 0;
	for (int i = 0; i < adj[here].size(); ++i) {
		int there = adj[here][i];
		if (discovered[there] == -1) {
			children++;
			int subTree = findCutVertex(there, false);
			if (!isRoot && subTree >= discovered[here]) // 자식이 자신보다 올라갈 수 없다면
				isCutVertex[here] = true;
			ret = min(ret, subTree);
		}
		else ret = min(ret, discovered[there]);
	}
	if (isRoot) isCutVertex[here] = (children >= 2);
	return ret;
}

* Cut Edge(절단선, 단절선)

  절단점을 작성하는 알고리즘을 변형하여 쉽게 구할 수 있다.

  정점 u에서 정점 v로 가는 간선이 있을 때, 이것이 단절선이 되기 위해서는 v를 루트로하는 자식트리가 갈 수 있는 최대한 작은 번호가 v를 방문한 discovered 번호면 된다.  u의 discovered값과 같거나 작으면 해당 간선은 절단선이 될 수 없다.

- 코드

vector<vector<int>> adj;
vector<int> discovered;
int counter;
vector<pair<int, int>> cutEdge;
int findCutEdge(int here, int parent) {
	discovered[here] = counter++;
	int ret = discovered[here];
	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		if (there == parent) continue;

		if (discovered[there] == -1) {
			int subTree = findCutEdge(there, here);
			if (discovered[here] < subTree) // 자식이 자신을 포함하여 올라갈 수 없다면
				cutEdge.push_back({ min(here,there)+1, max(here,there)+1 });
			ret = min(ret, subTree);
		}
		else ret = min(ret, discovered[there]);
	}
	return ret;
}