Articulation point(단절점) 구하는 알고리즘

아래 블로그에서 정말 많은 도움을 받았으며, 자세한 설명은 아래 블로그에 모두 있습니다!!!!

자세한 설명은 아래 글 참고

https://ttl-blog.tistory.com/956

[알고리즘] 그래프 (3) - 연결 요소(Connected Components)와 단절점(Articulation Point)

 

articulation point(cut vertex) : 어떤 G의 정점 u에 대하여 u와 연결된 모든 간선을 제거할 경우 G가 disconnect가 된다면 점 u를 G의 articulation point라고 정의한다.

 

Thm1) DFS Tree의 Root Node의 Child Node가 2개 이상이라면 root node는 articulation point이다.

Thm2) DFS Tree에서 아래 두 조건을 모두 만족하는 두 루트 노드가 아닌 노드 v, s가 존재할 경우 v는 articulation point이다.

i)  s가 v의 child node

ii) s의 descendant(s를 포함한 자손)와 v의 proper ancestor(v를 포함하지 않는 조상)를 연결하는 back edge가 존재X

Thm3) DFS Tree의 leaf node는 articulation point가 아니다.

 

■ DFS Tree : DFS를 수행할 때, 각 노드가 처음 발견된 순서에 따라 트리가 형성

출처 : https://ttl-blog.tistory.com/956

Articulation point

■ Discovery Time(pre) : 각 노드가 DFS를 통해 처음 방문된 시간 기록

■ Low Value : 노드 'v'에서 출발하여 역방향 간선을 통해 도달할 수 있는 가장 높은 조상노드의 discovery time 기록

 

step 1. DFS를 수행하여 discovery time(pre)와 low value(low)를 계산한다.

step 2. Low value 갱신 : low(v) = min(pre(v), pre(w))

노드 v의 자손 노드 u와 노드 u와 연결된 역방향 간선 (u, w)이 있을 때, v의 low value를 갱신

step 3. 루트 노드가 아닌 노드 v에 대해 자식노드 u의 low(u) >= pre(v)인 경우 v는 articulation point이다.

이 조건은 노드 v가 제거되었을 때, 노드 u와 그 자손들이 노드 v를 통해서만 다른 부분과 연결될 수 있음을 의미한다.

 

그래프 내 모든 Articulation point 찾는 알고리즘

* 모든 root node는 articulation point이다.

1. root node가 아닌 node들에 대하여 DFS를 수행하여 low 값을 업데이트 한다.

How? 초기 low(v) = pre(v)로 설정하고, 만약 back edge(v, u)가 있다면 low(v) = min(low(v), pre(u))로 업데이트한다.

v의 child u에 대하여 explore가 끝나면 low(v) = min(low(v), low(u))로 업데이트한다.

 

2. pre(v)와 low(u)를 비교하여 low(u) >= pre(v)인 경우 v는 articulation point이다.

 

코드는 처음 블로그에서 kotlin으로 짜여 있어 아래 페이지의 C++ 코드를 참고했다.

https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Articulation Points (or Cut Vertices) in a Graph - GeeksforGeeks

아래 코드에서 주의해야 할 점

1. adj는 const & 으로 전달해야 한다.그렇지 않으면 불필요한 복사가 발생해 메모리가 터진다.

2. if(parent != -1 && low[v] >= disc[u]) 조건을 주의하자

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

void APUtil(const vector<vector<int>>& adj,
	vector<bool>& visited,
	vector<bool>& isAP,
	vector<int>& disc,
	vector<int>& low,
	int u, int& time, int parent) {

	int children = 0;
	visited[u] = true;
	disc[u] = low[u] = ++time;

	for (int v : adj[u]) {
		if (!visited[v]) {
			children++;
			APUtil(adj, visited, isAP, disc, low, v, time, u);
			low[u] = min(low[u], low[v]);
			// 루트노드가 아닌 경우
			// u의 자식 v가 u를 통해서만 조상 노드에 갈 수 있는 경우 
			// low[v] >= disc[u] 
			// 자식 노드 v가 u를 거치지 않고는 조상 노드로 돌아갈 수 없다
			if (parent != -1 && low[v] >= disc[u]) isAP[u] = true;
		}
        // v가 u의 부모가 아닌 경우에만 back edge로 간주
		// 현재 노드 u에서 v로 가는 back edge가 존재한다면
		// u의 최소 도달 시간(low[u])을 v의 발견시간(disc[v])으로 갱신
		// 이를 통해 u가 절단점이 아니도록 한다.
		else if (v != parent) low[u] = min(low[u], disc[v]);
	}

	// 루트노드인 경우
	if (parent == -1 && children > 1) isAP[u] = true;
}

void findAPs(const vector<vector<int>>& adj, int V) {
	vector<bool> visited(V, false), isAP(V, false);
	vector<int> disc(V, -1), low(V, -1);
	int time = 0;

	for (int u = 0; u < V; u++) {
		if (!visited[u]) APUtil(adj, visited, isAP, disc, low, u, time, -1);
	}

	for (int u = 0; u < V; u++) {
		if (isAP[u]) cout << u << " ";
	}
	cout << "\n";

}

void addEdge(vector<vector<int>>& adj, int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

int main() {
	int V;

	cout << "Articulation points in first graph\n";
	V = 5;
	vector<vector<int>> adj1(V);
	addEdge(adj1, 1, 0);
	addEdge(adj1, 0, 2);
	addEdge(adj1, 2, 1);
	addEdge(adj1, 0, 3);
	addEdge(adj1, 3, 4);
	findAPs(adj1, V);

	cout << "\nArticulation points in second graph\n";
	V = 4;
	vector<vector<int>> adj2(V);
	addEdge(adj2, 0, 1);
	addEdge(adj2, 1, 2);
	addEdge(adj2, 2, 3);
	findAPs(adj2, V);

	cout << "\nArticulation points in third graph\n";
	V = 7;
	vector<vector<int>> adj3(V);
	addEdge(adj3, 0, 1);
	addEdge(adj3, 1, 2);
	addEdge(adj3, 2, 0);
	addEdge(adj3, 1, 3);
	addEdge(adj3, 1, 4);
	addEdge(adj3, 1, 6);
	addEdge(adj3, 3, 5);
	addEdge(adj3, 4, 5);
	findAPs(adj3, V);

	return 0;
}

 

단절선을 구하는 코드는 아래와 같다. 단절선을 구하기 위해서는 (low[v] > disc[u])인 u, v를 찾으면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void BridgeUtil(const vector<vector<int>>& adj, 
    int u, 
    vector<bool>& visited, 
    vector<int>& disc, 
    vector<int>& low, 
    int& time, 
    int parent) {
    visited[u] = true;
    disc[u] = low[u] = ++time;

    for (int v : adj[u]) {
        if (!visited[v]) {
            BridgeUtil(adj, v, visited, disc, low, time, u);

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

            if (low[v] > disc[u]) {
                cout << u << " -- " << v << " is a bridge\n";
            }
        }
        else if (v != parent) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void findBridges(const vector<vector<int>>& adj, int V) {
    vector<bool> visited(V, false);
    vector<int> disc(V, -1), low(V, -1);
    int time = 0;

    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            BridgeUtil(adj, u, visited, disc, low, time, -1);
        }
    }
}

void addEdge(vector<vector<int>>& adj, int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main() {
    int V;

    cout << "Bridges in first graph\n";
    V = 5;
    vector<vector<int>> adj1(V);
    addEdge(adj1, 1, 0);
    addEdge(adj1, 0, 2);
    addEdge(adj1, 2, 1);
    addEdge(adj1, 0, 3);
    addEdge(adj1, 3, 4);
    findBridges(adj1, V);

    cout << "\nBridges in second graph\n";
    V = 4;
    vector<vector<int>> adj2(V);
    addEdge(adj2, 0, 1);
    addEdge(adj2, 1, 2);
    addEdge(adj2, 2, 3);
    findBridges(adj2, V);

    cout << "\nBridges in third graph\n";
    V = 7;
    vector<vector<int>> adj3(V);
    addEdge(adj3, 0, 1);
    addEdge(adj3, 1, 2);
    addEdge(adj3, 2, 0);
    addEdge(adj3, 1, 3);
    addEdge(adj3, 1, 4);
    addEdge(adj3, 1, 6);
    addEdge(adj3, 3, 5);
    addEdge(adj3, 4, 5);
    findBridges(adj3, V);

    return 0;
}

 

아래는 백준 11400번 단절선 정답 코드이다!

https://www.acmicpc.net/problem/11400

 

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

void BridgeUtil(const vector<vector<int>>& adj,
	vector<bool>& visited,
	vector<int>& disc,
	vector<int>& low,
	int u, int& time, int parent, 
	stack<pair<int, int>>& st,
	vector<pair<int, int>>& bridges) {
	visited[u] = true;
	disc[u] = low[u] = time++;

	for (int v : adj[u]) {
		if (!visited[v]) {
			BridgeUtil(adj, visited, disc, low, v, time, u, st, bridges);
			low[u] = min(low[u], low[v]);

			if (low[v] > disc[u]) {
				if (u > v) bridges.push_back({ v, u });
				else bridges.push_back({ u, v });
			}
		}
		else if (v != parent) {
			low[u] = min(low[u], disc[v]);
		}
	}

}

void findBridge(const vector<vector<int>>& adj, int V) {
	vector<bool> visited(V, false);
	vector<int> disc(V, -1), low(V, -1);
	stack<pair<int, int>> st;
	vector<pair<int, int>> bridges;
	int time = 0;

	for (int i = 0; i < V; i++) {
		if (!visited[i]) BridgeUtil(adj, visited, disc, low, i, time, -1, st, bridges);
	}

	cout << bridges.size() << "\n";
	sort(bridges.begin(), bridges.end());
	for (pair<int, int> p : bridges) {
		cout << p.first+1 << " " << p.second+1 << "\n";
	}
}

void addEdge(vector<vector<int>>& adj, int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int V, E; cin >> V >> E;
	vector<vector<int>> adj(V);
	for (int i = 0; i < E; i++) {
		int A, B; cin >> A >> B;
		addEdge(adj, --A, --B);
	}
	findBridge(adj, V);
	return 0;
}