Bài viết này cũ, hãy đọc bài viết mới hơn
https://sites.google.com/site/kc97ble/algorithm-graph/tim-khop-va-cau
Tìm khớp và cầu trong đồ thị vô hướng
Mục đích : Tìm các cạnh hoặc các đỉnh mà khi loại bỏ chúng, đồ thị sẽ bị chia làm nhiều đồ thị con hơn (chính xác là nhiều thành phần liên thông hơn).
Độ phức tạp : O(n) hay O(|V|+|E|) (số cạnh cộng số đỉnh)
bridge.cpp
#include <stdio.h>
#include <vector>
using namespace std;
const int oo = 1000111000;
vector<int> a[2309];
int n, m;
int num[2309];
int low[2309];
int parent[2309];
int numChild[2309];
int cnt;
void minimize(int &a, int b) {
if (a > b) a = b;
}
void visit(int u) {
num[u] = ++cnt;
low[u] = oo;
for (int v : a[u])
if (v == parent[u])
continue; // keep direction
else if (num[v] > 0)
minimize(low[u], num[v]);
else {
parent[v] = u;
visit(v);
minimize(low[u], low[v]);
}
}
void visit() {
for (int i = 1; i <= n; i++)
if (num[i] == 0) {
parent[i] = -1;
visit(i);
}
}
void show() {
printf("node : ");
for (int i = 1; i <= n; i++) printf("%3d,", i);
printf("\n");
printf("num : ");
for (int i = 1; i <= n; i++) printf("%3d,", num[i]);
printf("\n");
printf("low : ");
for (int i = 1; i <= n; i++) printf("%3d,", low[i]);
printf("\n");
printf("parent : ");
for (int i = 1; i <= n; i++) printf("%3d,", parent[i]);
printf("\n");
for (int v = 1; v <= n; v++) // load all dfs edge
{
int u = parent[v];
if (u == -1) continue;
numChild[u]++;
if (low[v] >= num[v]) printf("bridge (%d-%d)\n", u, v);
}
for (int v = 1; v <= n; v++) {
int u = parent[v];
if (u == -1) { // if v is root
if (numChild[v] >= 2) printf("cut node (%d)\n", v);
} else if (low[v] >= num[u]) {
if (parent[u] != -1) // if u is not root
printf("cut vertex (%d)\n", u);
}
}
}
int main() {
scanf("%d%d", &n, &m);
while (m--) {
int p, q;
scanf("%d%d", &p, &q);
a[p].push_back(q);
a[q].push_back(p);
}
visit();
show();
}
Sample Input
4 4
1 2
2 3
3 4
4 2
Sample Output
node : 1, 2, 3, 4,
num : 1, 2, 3, 4,
low : 2, 2, 2, 2,
parent : -1, 1, 2, 3,
bridge (1-2)
cut vertex (2)
Thông tin khác
Ở bài viết này mình chỉ trình bày thuật toán tìm khớp và cầu ở đồ thị vô hướng, mong các bạn lưu ý.