Giới thiệu
Đồ thị song liên thông điểm (biconnected graph) và đồ thị song liên thông cạnh (edge-biconnected graph) là hai khái niệm quan trọng trong lý thuyết đồ thị. Một đồ thị được gọi là song liên thông điểm nếu việc loại bỏ bất kỳ một đỉnh nào (không phải hai đỉnh đang xét) không làm thay đổi tính liên thông của đồ thị. Tương tự, một đồ thị được gọi là song liên thông cạnh nếu việc loại bỏ bất kỳ một cạnh nào không làm thay đổi tính liên thông của đồ thị.
Song liên thông điểm và song liên thông cạnh
Trong một đồ thị vô hướng liên thông, hai đỉnh u và v được gọi là song liên thông cạnh nếu việc loại bỏ bất kỳ một cạnh nào (chỉ một cạnh) không làm chúng rời nhau.
Trong một đồ thị vô hướng liên thông, hai đỉnh u và v được gọi là song liên thông điểm nếu việc loại bỏ bất kỳ một đỉnh nào (chỉ một đỉnh, và không được loại bỏ chính u hoặc v) không làm chúng rời nhau.
Tính song liên thông cạnh có tính chất bắc cầu: nếu x song liên thông cạnh với y, và y song liên thông cạnh với z, thì x cũng song liên thông cạnh với z.
- Song liên thông điểm: Đồ thị vẫn liên thông sau khi loại bỏ một đỉnh.
- Song liên thông cạnh: Đồ thị vẫn liên thông sau khi loại bỏ một cạnh.
Tổng quan
Trong một đồ thị vô hướng, nếu giữa hai đỉnh bất kỳ luôn tồn tại ít nhất hai đường đi không đi qua đỉnh chung nào, thì đồ thị đó được gọi là song liên thông điểm.
Một thành phần con cực đại của đồ thị vô hướng mà song liên thông điểm được gọi là thành phần song liên thông điểm (Biconnected Component - BCC).
Tính chất
- Tồn tại ít nhất hai đường đi không đi qua đỉnh chung giữa hai đỉnh bất kỳ tương đương với việc loại bỏ bất kỳ một đỉnh nào không làm thay đổi tính liên thông của đồ thị, nghĩa là trong một BCC không có điểm khớp (articulation point).
- Nếu hai BCC có chung đỉnh, thì đỉnh chung đó là điểm khớp của đồ thị gốc.
- Trong một đồ thị vô hướng liên thông, một điểm khớp luôn thuộc ít nhất hai BCC, còn một đỉnh không phải điểm khớp chỉ thuộc một BCC duy nhất.
Thuật toán
Trong quá trình duyệt Tarjan, chúng ta sử dụng một ngăn xếp để lưu trữ các đỉnh. Khi thăm một đỉnh, chúng ta đẩy đỉnh đó vào ngăn xếp. Trong quá trình quay lui (backtrack), nếu giá trị low của đỉnh con không nhỏ hơn giá trị dfn của đỉnh cha, chúng ta sẽ lấy các đỉnh ra khỏi ngăn xếp cho đến khi gặp đỉnh con đó (bao gồm cả đỉnh con), và các đỉnh này cùng với đỉnh cha tạo thành một BCC.
Thành phần song liên thông điểm
Từ định nghĩa điểm khớp, ta biết rằng khi loại bỏ một điểm khớp, một thành phần liên thông mạnh có thể tách thành hai hoặc nhiều thành phần liên thông mạnh. Tuy nhiên, việc loại bỏ các đỉnh không phải điểm khớp không ảnh hưởng đến số lượng thành phần liên thông. Do đó, điểm khớp cùng với các đỉnh trong các thành phần liên thông mà nó phân chia có thể tạo thành một thành phần song liên thông điểm. Ví dụ:
Trong hình minh họa, các đỉnh 2 và 3 là điểm khớp. Ta nhận thấy {3, 6, 7} và {0, 1, 2, 3, 4, 5} là hai thành phần song liên thông điểm.
Dựa trên tính chất trên, một điểm khớp thuộc ít nhất hai thành phần song liên thông điểm. Vì vậy, khi lấy các phần tử ra khỏi ngăn xếp để lưu kết quả, chúng ta không lấy điểm khớp ra ngay, mà đợi cho đến khi tất cả các thành phần song liên thông điểm được phân chia bởi điểm khớp đó được tìm thấy, rồi mới thực hiện việc lấy các phần tử ra khỏi ngăn xếp.
Bài toán P8435 【模板】Thành phần song liên thông điểm
Mã nguồn:
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
const int MAXN = 100005; // Điều chỉnh kích thước cho phù hợp
std::vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN];
int timer;
std::stack<int> st;
std::vector<std::vector<int>> bccs;
bool visited[MAXN];
int component_count;
void find_bccs(int u, int p = -1) {
dfn[u] = low[u] = ++timer;
st.push(u);
visited[u] = true;
int children = 0;
for (int v : adj[u]) {
if (v == p) continue;
if (visited[v]) {
low[u] = std::min(low[u], dfn[v]);
} else {
children++;
find_bccs(v, u);
low[u] = std::min(low[u], low[v]);
// Điều kiện tìm thấy một BCC
if ((p != -1 && low[v] >= dfn[u]) || (p == -1 && children > 1)) {
component_count++;
std::vector<int> current_bcc;
while (true) {
int node = st.top();
st.pop();
current_bcc.push_back(node);
if (node == v) break;
}
current_bcc.push_back(u); // Thêm điểm khớp vào BCC
bccs.push_back(current_bcc);
}
}
}
// Xử lý trường hợp nút cô lập hoặc đồ thị chỉ có 1 đỉnh
if (p == -1 && !st.empty() && component_count == 0) {
component_count++;
std::vector<int> current_bcc;
while(!st.empty()){
current_bcc.push_back(st.top());
st.pop();
}
bccs.push_back(current_bcc);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
find_bccs(i);
}
}
std::cout << component_count << std::endl;
for (const auto& bcc : bccs) {
std::cout << bcc.size() << " ";
for (int node : bcc) {
std::cout << node << " ";
}
std::cout << std::endl;
}
return 0;
}
Một cách viết khác?
void find_bccs_alternative(int u, int p) {
dfn[u] = low[u] = ++timer;
st.push(u);
int children = 0;
for (int v : adj[u]) {
if (v == p) continue;
if (dfn[v] != 0) { // Đã thăm
low[u] = std::min(low[u], dfn[v]);
} else {
children++;
find_bccs_alternative(v, u);
low[u] = std::min(low[u], low[v]);
if (low[v] >= dfn[u]) {
component_count++;
std::vector<int> current_bcc;
int node;
do {
node = st.top();
st.pop();
current_bcc.push_back(node);
} while (node != v);
current_bcc.push_back(u);
bccs.push_back(current_bcc);
}
}
}
// Xử lý trường hợp nút cô lập hoặc đồ thị chỉ có 1 đỉnh
if (p == 0 && children == 0 && !st.empty()) {
component_count++;
std::vector<int> current_bcc;
while(!st.empty()){
current_bcc.push_back(st.top());
st.pop();
}
bccs.push_back(current_bcc);
}
}
Thành phần song liên thông cạnh
Cầu (bridge) là một cạnh mà khi loại bỏ nó, đồ thị sẽ không còn liên thông. Thuật toán để tìm cầu tương tự như tìm điểm khớp, nhưng có một sự khác biệt nhỏ trong điều kiện: thay vì if(low[v] >= dfn[x]), ta sử dụng if(low[v] > dfn[x]).
Khi loại bỏ các cầu, đồ thị sẽ được chia thành nhiều thành phần liên thông. Nếu một cạnh không phải là cầu, nó không ảnh hưởng đến số lượng thành phần liên thông. Do đó, chúng ta có thể tìm tất cả các cầu, đánh dấu chúng, sau đó thực hiện duyệt DFS để tìm các thành phần liên thông cạnh.
Quan sát đồ thị dưới đây:
Các cạnh không phải là cầu là {1, 3}, {1, 2}, {2, 3}. Ta nhận thấy trong một thành phần song liên thông cạnh (DCC), không có cạnh nào là cầu. Do đó, việc đánh dấu các cầu và thực hiện DFS là hoàn toàn chính xác.
Bài toán P8436 【模板】Thành phần song liên thông cạnh
Mã nguồn:
#include <iostream>
#include <vector>
#include <algorithm>
const int MAXN = 2000005; // Điều chỉnh kích thước cho phù hợp
std::vector<std::pair<int, int>> adj[MAXN]; // Lưu đỉnh và chỉ số cạnh
int dfn[MAXN], low[MAXN];
int timer;
int component_count; // Số lượng thành phần song liên thông cạnh
bool visited[MAXN];
std::vector<std::vector<int>> dccs; // Lưu các thành phần song liên thông cạnh
struct Edge {
int to;
bool is_bridge;
};
std::vector<Edge> graph[MAXN]; // Biểu diễn đồ thị với cờ đánh dấu cầu
void find_bridges(int u, int p = -1) {
dfn[u] = low[u] = ++timer;
for (const auto& edge : graph[u]) {
int v = edge.to;
if (v == p) continue;
if (dfn[v] != 0) { // Đã thăm
low[u] = std::min(low[u], dfn[v]);
} else {
find_bridges(v, u);
low[u] = std::min(low[u], low[v]);
if (low[v] > dfn[u]) {
// Đánh dấu cạnh là cầu
for(auto& e : graph[u]) if(e.to == v) e.is_bridge = true;
for(auto& e : graph[v]) if(e.to == u) e.is_bridge = true;
}
}
}
}
void build_graph_with_bridges(int n, int m, const std::vector<std::pair<int, int>> edges[]) {
for (int i = 1; i <= n; ++i) graph[i].clear();
for (int u = 1; u <= n; ++u) {
for (auto& edge : edges[u]) {
int v = edge.first;
graph[u].push_back({v, false}); // Ban đầu không đánh dấu là cầu
}
}
}
void dfs_dcc(int u) {
visited[u] = true;
dccs[component_count].push_back(u);
for (const auto& edge : graph[u]) {
int v = edge.to;
if (!visited[v] && !edge.is_bridge) {
dfs_dcc(v);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
std::vector<std::pair<int, int>> input_adj[MAXN];
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
input_adj[u].push_back({v, i});
input_adj[v].push_back({u, i});
graph[u].push_back({v, false}); // Khởi tạo đồ thị cho tìm cầu
graph[v].push_back({u, false});
}
// Tìm các cầu
timer = 0;
for (int i = 1; i <= n; ++i) {
dfn[i] = 0; // Reset dfn
if (dfn[i] == 0) {
find_bridges(i);
}
}
// Tìm các thành phần song liên thông cạnh bằng DFS
component_count = -1; // Bắt đầu từ -1 để index dccs bắt đầu từ 0
for (int i = 1; i <= n; ++i) visited[i] = false; // Reset visited
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
component_count++;
dccs.emplace_back(); // Thêm một thành phần mới
dfs_dcc(i);
}
}
std::cout << component_count + 1 << std::endl; // +1 vì component_count bắt đầu từ 0
for (int i = 0; i <= component_count; ++i) {
std::cout << dccs[i].size() << " ";
for (int node : dccs[i]) {
std::cout << node << " ";
}
std::cout << std::endl;
}
return 0;
}