684. Redundant Connection

解題思路

用 union find 來解這題。

如果 edge 的兩個 node 已屬於同個 union，即可知該 edge 為多餘的。

程式碼

class Solution {
public:
    int *dsu, *rank;
    int size;

    int find_set(int v)
    {
        if(dsu[v] == v) return v;
        return dsu[v] = find_set(dsu[v]);
    }
    void make_union(int u, int v)
    {
        u = find_set(u), v = find_set(v);
        if(u != v)
        {
            if(rank[u] > rank[v])
            {
                dsu[v] = u;
                rank[u] += rank[v]; 
            }
            else
            {
                dsu[u] = v;
                rank[v] += rank[u]; 
            }
        }
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        this->size = edges.size() + 1;
        this->dsu = new int[size];
        this->rank = new int[size];

        for(int i=0; i<size; i++)
        {
            dsu[i] = i;
            rank[i] = 1;
        }

        for(int i=0; i<edges.size(); i++)
        {
            if(find_set(edges[i][0]) == find_set(edges[i][1]))
                return edges[i];
            make_union(edges[i][0], edges[i][1]);
        }    
        return edges[0];
    }
};