Hiểu bài toán

Bài toán yêu cầu tìm số lượng con đường tối thiểu cần thêm vào một đồ thị không có hướng ban đầu để đồ thị trở thành liên thông. Ban đầu đồ thị có N đỉnh và M cạnh. Các cạnh có thể được thêm vào giữa bất kỳ cặp đỉnh nào chưa có cạnh trực tiếp. Tuy nhiên, ta không cần quan tâm đến điều kiện "chưa có cạnh trực tiếp" nếu chỉ xét số lượng cạnh tối thiểu, vì ta có thể thêm cạnh giữa các đỉnh trong các thành phần liên thông khác nhau để kết nối chúng. Yêu cầu là làm sao toàn bộ đồ thị sau khi thêm cạnh trở thành một thành phần liên thông duy nhất.

Các cách tiếp cận

Cách Duyệt đồ thị (DFS/BFS) để đếm thành phần liên thông

#include <iostream>
#include <vector>
using namespace std;
const int nmax = 1e5+1; 
vector<int> a[nmax];
int cnt = 0; 
bool vis[nmax] = {0};

void dfs(int i) 
{
    vis[i] = 1; 
    for (auto j: a[i]) {
        if (j != i && !vis[j]) {
            dfs(j); 
        }
    }
}

int main()
{
    int n, m; 
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; 
        cin >> x >> y; 
        a[x].push_back(y);
        a[y].push_back(x); 
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cnt++; 
            dfs(i); 
        }
    }
    cout << cnt - 1; 
    return 0; 
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Cách tiếp cận này sử dụng thuật toán DFS (hoặc BFS) để duyệt qua tất cả các đỉnh của đồ thị. Ta duy trì một mảng đánh dấu vis để kiểm tra xem một đỉnh đã được duyệt chưa. Khi gặp một đỉnh chưa được duyệt, ta bắt đầu một lần duyệt DFS mới từ đỉnh đó và tăng biến đếm cnt lên 1. Biến cnt sẽ lưu số lượng thành phần liên thông của đồ thị. Để kết nối cnt thành phần liên thông này lại với nhau, ta cần ít nhất cnt - 1 con đường mới (giống như xây dựng một cây khung Spanning Tree trên các thành phần liên thông).

Cách Cấu trúc dữ liệu Disjoint Set Union (DSU)

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

const int MAX = 1e5 + 5;
int parent[MAX];

void makeSet(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}

int findSet(int u) {
    while (u != parent[u]) {
        parent[u] = parent[parent[u]];
        u = parent[u];
    }
    return u;
}

void unionSet(int u, int v) {
    int pu = findSet(u);
    int pv = findSet(v);
    if (pu != pv) {
        parent[pv] = pu;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    makeSet(N);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        unionSet(A, B);
    }

    unordered_set<int> components;
    for (int i = 1; i <= N; i++) {
        components.insert(findSet(i));
    }

    int numComponents = components.size();
    cout << numComponents - 1;
    return 0;
}

• Time Complexity: O((N + M) * \alpha(N)) ~ O(N + M)
• Space Complexity: O(N)

DSU (Disjoint Set Union) là cấu trúc dữ liệu lý tưởng để xử lý bài toán liên quan đến các tập hợp phân biệt và hợp nhất chúng. Ban đầu, mỗi đỉnh là một tập hợp riêng biệt. Với mỗi cạnh (u, v) trong input, ta thực hiện phép union(u, v) để hợp nhất hai tập hợp chứa u và v. Sau khi xử lý hết M cạnh, ta duyệt qua tất cả các đỉnh, tìm đại diện của chúng (findSet) và lưu vào một set để đếm số lượng tập hợp (tức số thành phần liên thông). Số cạnh cần thêm là số_thành_phần - 1. DSU thường được tối ưu với Path Compression và Union by Rank, nhưng code mẫu chỉ dùng Path Compression cũng đủ nhanh.

Cách Sử dụng mảng đánh dấu thành phần

// LonggVuz.
#include<bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 7;

int n, m, r[mxn];

int get(int u){
    if(r[u] == u) return u;
    return r[u] = get(r[u]);
}

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) r[i] = i;
    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y;
        x = get(x); y = get(y);
        r[y] = x;
    }
    set<int> s;
    for(int i=1; i<=n; i++){
        int x = get(i);
        {s.is(x);}
    }
    cout << s.size() - 1;
    return 0;
}

• Time Complexity: O(N + M) trong thực tế (với Path Compression)
• Space Complexity: O(N)

Đây là biến thể của DSU. Code sử dụng mảng r (representative hoặc parent). Hàm get thực hiện tìm kiếm với nén đường. Logic cơ bản giống DSU: đọc cạnh, hợp nhất. Cuối cùng, ta duyệt qua các đỉnh, lấy đại diện của đỉnh đó và thêm vào một set. Kích thước của set chính là số thành phần liên thông. Số cạnh cần thêm là s.size() - 1. Đây là cách tiếp cận hiệu quả và phổ biến nhất trong cạnh tranh.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Để biến một đồ thị có nhiều thành phần liên thông thành một đồ thị liên thông duy nhất, số cạnh tối thiểu cần thêm vào bằng (Số thành phần liên thông - 1).
• Bài toán này có thể được giải quyết bằng cách đếm số thành phần liên thông.
• DSU (Disjoint Set Union) là công cụ mạnh mẽ và hiệu quả nhất cho các bài toán về thành phần liên thông và kết nối.

Lỗi thường gặp

• Quên trường hợp đồ thị ban đầu đã liên thông (Số thành phần = 1, kết quả là 0).
• Sử dụng thuật toán duyệt (DFS/BFS) không tối ưu có thể gây tràn bộ nhớ (Stack Overflow) hoặc chạy chậm nếu không dùng danh sách kề.
• Lỗi cài đặt DSU: Quên nén đường (Path Compression) có thể khiến độ phức tạp tăng lên O(log N) hoặc tệ hơn, dẫn đến quá thời gian (TLE) với dữ liệu lớn.