Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        map<PII, int> edge2index;
        vector<vector<int>> graph(n+1);
        vector<int> degree(n+1);
        vector<int> visited(n+1, 0);

        for(int i = 0; i < edges.size(); ++i) {
            edge2index[{edges[i][0], edges[i][1]}] = i;
            edge2index[{edges[i][1], edges[i][0]}] = i;
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
            ++degree[edges[i][1]];
            ++degree[edges[i][0]];
        }

        queue<int> q;
        for(int i = 1; i <= n; ++i) {
            if(degree[i] == 1) q.push(i);
        }

        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            if(visited[cur]) continue;
            visited[cur] = 1;

            for(auto x: graph[cur]) {
                if(visited[x]) continue;
                --degree[x];

                if(degree[x] == 1) q.push(x);
            }
        }

        auto cmp = [&edge2index](PII& p1, PII& p2) {
            return edge2index[p1] < edge2index[p2];
        };
        priority_queue<PII, vector<PII>, decltype(cmp)> pq(cmp);
        for(int i = 0; i < n; ++i) {
            if(visited[i]) continue;

            for(auto x: graph[i]) {
                if(visited[x] || x < i) continue;
                pq.emplace(i, x);
            }
        }

        return edges[edge2index[pq.top()]];
    }
};

class Solution {
    vector<int> father;

    void ufInit(int n) {
        father.resize(n);
        for(int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }

    int ufFind(int n) {
        if(n == father[n]) return n;
        return father[n] = ufFind(father[n]);
    }

    void ufUnion(int a, int b) {
        int x = ufFind(a);
        int y = ufFind(b);
        father[x] = y;
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();   // number of nodes

        ufInit(n+1);

        for(auto& e: edges) {
            if(ufFind(e[0]) == ufFind(e[1])) return e;
            ufUnion(e[0], e[1]);
        }
        
        return {};
    }
};