Bài toán
Đếm số lượng thành phần liên thông mạnh trên đồ thị có hướng.
Thành phần liên thông mạnh là một tập hợp các đỉnh mà với bất cứ cặp u, v nào, ta luôn có u đi tới được v và v đi tới được u (có thể qua một số đỉnh trung gian). Khi phân tích một đồ thị ra thành phần liên thông mạnh, mỗi TPLTM phải là cực đại, nghĩa là không thể thêm bất cứ đỉnh nào vào một TPLTM mà vẫn tạo thành TPLTM.
Độ phức tạp
O(n+m)
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int N = 100005;
const int oo = 0x3c3c3c3c;
int n, m, Num[N], Low[N], cnt = 0;
vector<int> a[N];
stack<int> st;
int Count = 0;
void visit(int u) {
Low[u] = Num[u] = ++cnt;
st.push(u);
for (int v : a[u])
if (Num[v])
Low[u] = min(Low[u], Num[v]);
else {
visit(v);
Low[u] = min(Low[u], Low[v]);
}
if (Num[u] == Low[u]) { // found one
Count++;
int v;
do {
v = st.top();
st.pop();
Num[v] = Low[v] = oo; // remove v from graph
} while (v != u);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!Num[i]) visit(i);
cout << Count << endl;
}
Nhận xét
Code này đã được dùng để nộp cho một bài trên SPOJ.
Tham khảo
http://vn.spoj.com/problems/TJALG/
https://codeforces.com/group/FLVn1Sc504/contest/274834/problem/K
Mô tả
int Num[]
Num[u] là thời gian thăm nút u trong quá trình duyệt DFS
int Low[]
Tưởng tượng, khi xuất phát từ u, đi qua một số cung trên cây DFS, và nhiều nhất một cung ngược, ta được một danh sách tập hợp các nút đến được. Low[u] là Num[x] nhỏ nhất trong tất cả các x nằm trong tập này.
Đánh giá
Các bạn có thể đánh giá bài viết hoặc gửi nhận xét tại đây.
http://goo.gl/forms/ls88qsPHgi