Kết nối dư thừa trong C++

Giới thiệu

Cho đồ thị vô hướng bắt đầu là cây N nút (1..N), thêm 1 cạnh tạo thành chu trình. Tìm cạnh có thể xóa để đồ thị trở lại cây. Nếu nhiều đáp án, chọn cạnh xuất hiện cuối cùng trong danh sách đầu vào.

Thuật toán: Union-Find (Disjoint Set Union)

Duyệt các cạnh theo thứ tự. Với mỗi cạnh (u, v):

• Nếu u và v đã cùng tập (find(u) == find(v)) → cạnh này tạo chu trình → là cạnh dư thừa.
• Ngược lại, union(u, v).

Vì duyệt theo thứ tự, cạnh dư thừa cuối cùng sẽ được ghi đè lên đáp án.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) : parent(n+1), rank(n+1, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        DSU dsu(1000); // N <= 1000
        vector<int> ans;
        for (auto& e : edges) {
            if (!dsu.unite(e[0], e[1])) ans = e;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> edges = {{1,2},{2,3},{3,4},{1,4},{1,5}};
    auto ans = ob.findRedundantConnection(edges);
    cout << '[' << ans[0] << ',' << ans[1] << ']'; // Output: [1,4]
    return 0;
}

Phân tích

• Thời gian: O(N α(N)) ≈ O(N) – α là hàm Ackermann nghịch đảo.
• Không gian: O(N).

Đây là bài toán kinh điển LeetCode 684 "Redundant Connection".