题解 | 冗余连接

题干解析

题设要求我们找出一个联通图的冗余边。

算法思路

本题是关于并查集数据结构的经典应用。利用并查集的性质，我们在构建图的同时检查当前构建的边是否为冗余边，不是冗余边则将该边两端点在并查集中进行连接，是冗余边则记录。由于题设要求我们输出最后出现的一条冗余边，因此我们不能一找到冗余边就输出，需要完全遍历整个题设的连接数组。

实现代码

class L684 {
    class UnionFind { // 这是优化连接的并查集类，一般使用可以不用考虑秩
        vector<int> parent;
        vector<int> rank; // 秩（树高度近似值）

    public:
        explicit UnionFind(const int n) : parent(n), rank(n, 0) {
            iota(parent.begin(), parent.end(), 0); // C++11初始化
        }

        int find(int x) {
            // 迭代路径压缩（更节省栈空间）
            while (parent[x] != x) {
                parent[x] = parent[parent[x]]; // 路径减半压缩
                x = parent[x];
            }
            return x;
        }

        void unite(const int x, const int y) {
            const int rootX = find(x);
            const int rootY = find(y);

            if (rootX == rootY) return;

            // 按秩合并：小树挂到大树
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++; // 高度相同才增加
            }
        }

        bool isConnected(const int x, const int y) {
            return find(x) == find(y);
        }
    };

public:
    vector<int> findRedundantConnection(vector<vector<int> > &edges) {
        vector<int> ans;
        UnionFind uf(static_cast<int>(edges.size()));
        for (auto vPair: edges) {
            if (uf.isConnected(vPair[0] - 1, vPair[1] - 1)) ans = vPair;
            else uf.unite(vPair[0] - 1, vPair[1] - 1);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度： 并查集每次查找与联合都是的时间复杂度，共计次，为常数。故时间复杂度为，其中为阿克曼函数的反函数，可以认为是一个很小的常数。
• 空间复杂度： 主要额外空间为parent数组与rank数组消耗，二者均为