Hướng dẫn giải của Thành phần liên thông
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
, , ,
Editorial for compconn: Thành phần liên thông
Hiểu bài toán
Bài toán yêu cầu tìm và liệt kê tất cả các thành phần liên thông của một đồ thị vô hướng. Một thành phần liên thông là một tập hợp các đỉnh sao cho giữa mọi cặp đỉnh trong tập đó đều có đường đi, và tập này là lớn nhất có thể (không thể thêm đỉnh nào khác mà vẫn giữ tính liên thông). Đầu vào gồm số đỉnh n, số cạnh m, và m cạnh nối giữa các đỉnh. Đầu ra cần in ra số lượng thành phần liên thông, sau đó liệt kê từng thành phần theo thứ tự tăng dần của các đỉnh, với mỗi dòng bắt đầu bằng số lượng đỉnh của thành phần đó.
Các cách tiếp cận
Cách Duyệt theo chiều sâu (DFS)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
vector<int> adj[MAXN];
bool visited[MAXN];
void dfs(int u, vector<int>& component) {
visited[u] = true;
component.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v, component);
}
}
}
int main() {
ios::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);
adj[v].push_back(u);
}
vector<vector<int>> components;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
vector<int> component;
dfs(i, component);
sort(component.begin(), component.end());
components.push_back(component);
}
}
cout << components.size() << "\n";
for (const auto& comp : components) {
cout << comp.size();
for (int u : comp) {
cout << " " << u;
}
cout << "\n";
}
return 0;
}
- Time Complexity: O(n + m)
- Space Complexity: O(n + m)
Đây là cách tiếp cận trực quan nhất. Ta sử dụng một mảng đánh dấu visited để theo dõi các đỉnh đã được thăm. Duyệt qua từng đỉnh từ 1 đến n. Nếu đỉnh đó chưa được thăm, thực hiện DFS từ đỉnh đó. Trong quá trình DFS, ta thu thập tất cả các đỉnh thuộc cùng một thành phần liên thông vào một vector. Sau khi DFS hoàn tất, sắp xếp vector này (theo yêu cầu đề bài) và lưu vào danh sách kết quả. Complexity là O(n + m) vì mỗi đỉnh và cạnh chỉ được xử lý tối đa một lần.
Cách Duyệt theo chiều rộng (BFS)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
vector<int> adj[MAXN];
bool visited[MAXN];
void bfs(int start, vector<int>& component) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
component.push_back(u);
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
int main() {
ios::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);
adj[v].push_back(u);
}
vector<vector<int>> components;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
vector<int> component;
bfs(i, component);
sort(component.begin(), component.end());
components.push_back(component);
}
}
cout << components.size() << "\n";
for (const auto& comp : components) {
cout << comp.size();
for (int u : comp) {
cout << " " << u;
}
cout << "\n";
}
return 0;
}
- Time Complexity: O(n + m)
- Space Complexity: O(n + m)
Cách tiếp cận này tương tự DFS nhưng sử dụng thuật toán BFS (Duyệt theo chiều rộng). Sử dụng một hàng đợi (queue) để quản lý các đỉnh cần duyệt. Khi gặp một đỉnh chưa được thăm, ta thêm nó vào hàng đợi và đánh dấu đã thăm. BFS sẽ lần lượt duyệt qua các đỉnh kề, đảm bảo tìm hết tất cả đỉnh trong cùng một thành phần liên thông. Kết quả thu được tương tự DFS.
Cách DSU (Disjoint Set Union)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int parent[MAXN];
int sz[MAXN];
int find_set(int v) {
if (v == parent[v]) return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
sz[i] = 1;
}
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
union_sets(u, v);
}
map<int, vector<int>> components;
for (int i = 1; i <= n; i++) {
components[find_set(i)].push_back(i);
}
cout << components.size() << "\n";
for (auto& pair : components) {
cout << pair.second.size();
for (int u : pair.second) {
cout << " " << u;
}
cout << "\n";
}
return 0;
}
- Time Complexity: O((n + m) * α(n))
- Space Complexity: O(n)
DSU (Cấu trúc dữ liệu Union-Find) là một cách tiếp cận khác. Ban đầu, mỗi đỉnh là một tập hợp riêng biệt. Khi đọc từng cạnh (u, v), ta thực hiện lệnh union(u, v) để hợp nhất hai tập hợp chứa u và v. Sau khi xử lý hết các cạnh, các đỉnh trong cùng một thành phần liên thông sẽ thuộc cùng một tập hợp. Ta duyệt qua tất cả các đỉnh, dùng hàm find để xác định đại diện của tập hợp, và nhóm các đỉnh lại theo đại diện này. DSU thường được dùng khi bài toán chỉ cần đếm số thành phần hoặc kiểm tra tính liên thông, nhưng ở đây ta cần liệt kê đỉnh nên phải thêm bước thu thập.
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) | Duyệt theo chiều sâu (DFS) |
| 2 | O(n + m) | O(n + m) | Duyệt theo chiều rộng (BFS) |
| 3 | O((n + m) * α(n)) | O(n) | DSU (Disjoint Set Union) |
Bài học kinh nghiệm
- Một thành phần liên thông là một tập hợp các đỉnh được kết nối với nhau qua các cạnh. Để tìm tất cả, ta chỉ cần bắt đầu duyệt từ một đỉnh chưa được duyệt bất kỳ.
- DFS và BFS là hai thuật toán chuẩn để duyệt các đỉnh liên thông khi đã bắt đầu từ một đỉnh.
- DSU là một cấu trúc dữ liệu mạnh mẽ để xử lý các bài toán về tập hợp liên thông (Connected Components).
Lỗi thường gặp
- Quên đánh dấu đỉnh đã duyệt (visited) dẫn đến lặp vô hạn hoặc sai lệch thành phần liên thông.
- Không sắp xếp lại danh sách các đỉnh trong thành phần liên thông trước khi in ra (theo yêu cầu đề bài).
- Quên ghi nhận cạnh (u, v) phải lưu vào danh sách kề cả hai chiều u -> v và v -> u trong đồ thị vô hướng.
Bình luận