684 Redundant Connection

In this problem, a tree is anundirectedgraph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array ofedges. Each element ofedgesis a pair[u, v]withu < v, that represents anundirectededge connecting nodesuandv.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge[u, v]should be in the same format, withu < v.

Example 1:

Input:
 [[1,2], [1,3], [2,3]]

Output:
 [2,3]

Explanation:
 The given undirected graph will be like this:
  1
 / \
2 - 3

Example 2:

Input:
 [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output:
 [1,4]

Explanation:
 The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3

Note:

The size of the input 2D-array will be between 3 and 1000.

Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

The Idea: This is a disjoint set problem, which is essentially used for the purpose of identifying a cycle in an undirected graph. What we do is continuously perform a union on each (i,j) if both i and j are already not in the same union. If they are, they are the cause of the cycle.

Complexity: O(n) (bounded by Inverse Ackermann)

struct Node {
    Node(const int id) : id(id), parent(this), depth(0) {};
    int depth;
    const int id;
    Node *parent;
};

class DisjointSet {
public:

    DisjointSet(const int ids) : num_ids(ids) {
        init_find.reserve(ids);
        for (int i = 1; i <= ids; i++)
            make_set(i);
    }

    int find(const int x) {
        if (init_find.find(x) == init_find.end()) return -1;
        else return _find(x);
    }

    void union_(const int x, const int y) {
        int x_parent = find(x);
        int y_parent = find(y);
        if (init_find[y_parent]->depth <= init_find[x_parent]->depth)
            init_find[y_parent]->parent = init_find[x_parent]->parent;

        else if (init_find[y_parent]->depth > init_find[x_parent]->depth)
            init_find[x_parent]->parent = init_find[y_parent]->parent;

        if (init_find[y_parent]->depth == init_find[x_parent]->depth)
            init_find[x_parent]->depth++;
    }

private:
    const size_t num_ids;

    void make_set(const int x) {
        if (init_find.find(x) != init_find.end()) return;
        else init_find.insert({ x, new Node(x) });
    }

    int _find(const int x) {
        Node *iter = init_find[x]->parent;

        if (iter->id == iter->parent->id) {
            return iter->id;
        }
        else {
            // path compression
            while (iter->id != iter->parent->id)
                iter = iter->parent;
            init_find[x]->parent = init_find[iter->id];
            return iter->id;
        }
    }

    unordered_map<int, Node*> init_find;
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        DisjointSet ds(edges.size());
        for (vector<int> &v : edges) {
            int a_find = ds.find(v[0]);
            int b_find = ds.find(v[1]);
            if (a_find == b_find) {
                return v;
            }
            else {
                ds.union_(v[0], v[1]);
            }
        }
    }
};