Hướng dẫn giải của Liên thông
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu đếm số thành phần liên thông mạnh (Strongly Connected Components - SCC) trong một đồ thị có hướng. INPUT: hai số nguyên N (số đỉnh) và M (số cạnh), tiếp theo là M cặp cạnh (u, v) thể hiện đường nối từ u đến v. OUTPUT: số lượng thành phần liên thông mạnh của đồ thị.
Các cách tiếp cận
Cách Thuật toán Kosaraju (2 lần DFS)
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> adj[105], rev[105];
bool visited[105];
stack<int> st;
void dfs1(int u) {
visited[u] = true;
for (int v : adj[u])
if (!visited[v])
dfs1(v);
st.push(u);
}
void dfs2(int u) {
visited[u] = true;
for (int v : rev[u])
if (!visited[v])
dfs2(v);
}
int main() {
ifstream fin("LIENTHONG.INP");
ofstream fout("LIENTHONG.OUT");
fin >> n >> m;
for(int i=0; i<m; i++) {
int u, v; fin >> u >> v;
adj[u].push_back(v);
rev[v].push_back(u);
}
memset(visited, false, sizeof(visited));
for (int i = 1; i <= n; i++)
if (!visited[i]) dfs1(i);
memset(visited, false, sizeof(visited));
int cnt = 0;
while (!st.empty()) {
int u = st.top(); st.pop();
if (!visited[u]) {
cnt++;
dfs2(u);
}
}
fout << cnt;
return 0;
}
- Time Complexity: O(N + M)
- Space Complexity: O(N + M)
Thuật toán Kosaraju thực hiện 2 bước:
- DFS trên đồ thị gốc để đẩy các đỉnh vào stack theo thứ tự hoàn thành (post-order).
- Lật đồ thị (tạo đồ thị ngược) và lần lượt lấy đỉnh ra khỏi stack, thực hiện DFS trên đồ thị ngược đối với các đỉnh chưa duyệt. Mỗi lần gọi DFS2 tương ứng với một thành phần liên thông mạnh.
Cách Thuật toán Tarjan (DFS một lần)
#include <bits/stdc++.h>
using namespace std;
int n, m, node = 0, res = 0;
int id[1000005], low[1000005];
bool vst[1000005];
stack<int> st;
vector<int> adj[1000005];
void Tarjan(int u) {
id[u] = low[u] = ++node;
st.push(u);
vst[u] = true;
for (int v : adj[u]) {
if (id[v] == 0) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vst[v]) {
low[u] = min(low[u], id[v]);
}
}
if (low[u] == id[u]) {
res++;
while (true) {
int v = st.top(); st.pop();
vst[v] = false;
if (u == v) break;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; i++)
if (id[i] == 0) Tarjan(i);
cout << res;
return 0;
}
- Time Complexity: O(N + M)
- Space Complexity: O(N + M)
Tarjan sử dụng một lần duyệt DFS duy nhất. Nó theo dõi 'id' (thứ tự duyệt) và 'low' (id thấp nhất có thể đến được).
- Khi một đỉnh u thỏa mãn low[u] == id[u], u là đỉnh của một SCC.
- Các đỉnh trong SCC được lấy ra từ stack cho đến khi gặp u.
- Đây là thuật toán thường có hiệu năng thực tế tốt hơn Kosaraju do chỉ duyệt đồ thị một lần.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N + M) | O(N + M) | Thuật toán Kosaraju (2 lần DFS) |
| 2 | O(N + M) | O(N + M) | Thuật toán Tarjan (DFS một lần) |
Bài học kinh nghiệm
- Cấu trúc dữ liệu stack là cần thiết để lưu trữ các đỉnh trong đường đi hiện tại hoặc theo thứ tự hoàn thành.
- Một SCC có thể được coi là một 'đỉnh' của đồ thị DAG (Directed Acyclic Graph) sau khi gom nhóm.
Lỗi thường gặp
- Quên khởi tạo mảng visited hoặc id về 0 (giá trị mặc định của mảng全局 hoặc dùng memset).
- Sử dụng sai giới hạn (N) khi khai báo mảng động (ví dụ n <= 10^5 nhưng khai báo mảng nhỏ).
- Xử lý sai input/output khi làm bài có file (ifstream/ofstream).
Bình luận