Java

/**

 In this problem, a tree is an undirected graph 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 of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

 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, with u < 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.

 */

public class Redundant_Connection {

}

// OJ: https://leetcode.com/problems/redundant-connection/
// Time: O(N)
// Space: O(N)
class UnionFind {
private:
  vector<int> id, rank;
  int cnt;
public:
  UnionFind(int cnt) : cnt(cnt) {
    id = vector<int>(cnt);
    rank = vector<int>(cnt, 0);
    for (int i = 0; i < cnt; ++i) id[i] = i;
  }
  int find(int p) {
      if (id[p] == p) return p;
      return id[p] = find(id[p]);
  }
  int getCount() { return cnt; }
  bool connected(int p, int q) { return find(p) == find(q); }
  void connect(int p, int q) {
    int i = find(p), j = find(q);
    if (i == j) return;
    if (rank[i] < rank[j]) id[i] = j;
    else {
      id[j] = i;
      if (rank[i] == rank[j]) rank[j]++;
    }
    --cnt;
  }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind uf(edges.size());
        for (auto e : edges) {
            if (uf.connected(e[0] - 1, e[1] - 1)) return e;
            uf.connect(e[0] - 1, e[1] - 1);
        }
    }
};

class Solution:
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        tree = [-1] * (len(edges) + 1)
        for edge in edges:
            a = self.findRoot(edge[0], tree)
            b = self.findRoot(edge[1], tree)
            if a != b:
                tree[a] = b
            else:
                return edge
        
        
    def findRoot(self, x, tree):
        if tree[x] == -1: return x
        else:
            root = self.findRoot(tree[x], tree)
            tree[x] = root
            return root

Java

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] redundantConnection = new int[2];
        Map<Integer, Integer> nodeGroupMap = new HashMap<Integer, Integer>();
        Map<Integer, Set<Integer>> groupNodesMap = new HashMap<Integer, Set<Integer>>();
        int nodesCount = edges.length;
        for (int i = 1; i <= nodesCount; i++) {
            nodeGroupMap.put(i, i);
            Set<Integer> set = new HashSet<Integer>();
            set.add(i);
            groupNodesMap.put(i, set);
        }
        for (int i = 0; i < nodesCount; i++) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            int group1 = nodeGroupMap.getOrDefault(node1, node1);
            int group2 = nodeGroupMap.getOrDefault(node2, node2);
            if (group1 == group2) {
                redundantConnection[0] = node1;
                redundantConnection[1] = node2;
                break;
            } else {
                Set<Integer> set1 = groupNodesMap.getOrDefault(group1, new HashSet<Integer>());
                Set<Integer> set2 = groupNodesMap.getOrDefault(group2, new HashSet<Integer>());
                if (group1 < group2) {
                    set1.addAll(set2);
                    for (int node : set2)
                        nodeGroupMap.put(node, group1);
                    groupNodesMap.put(group1, set1);
                } else {
                    set2.addAll(set1);
                    for (int node : set1)
                        nodeGroupMap.put(node, group2);
                    groupNodesMap.put(group2, set2);
                }
            }
        }
        return redundantConnection;
    }
}

// OJ: https://leetcode.com/problems/redundant-connection/
// Time: O(N)
// Space: O(N)
class UnionFind {
private:
  vector<int> id, rank;
  int cnt;
public:
  UnionFind(int cnt) : cnt(cnt) {
    id = vector<int>(cnt);
    rank = vector<int>(cnt, 0);
    for (int i = 0; i < cnt; ++i) id[i] = i;
  }
  int find(int p) {
      if (id[p] == p) return p;
      return id[p] = find(id[p]);
  }
  int getCount() { return cnt; }
  bool connected(int p, int q) { return find(p) == find(q); }
  void connect(int p, int q) {
    int i = find(p), j = find(q);
    if (i == j) return;
    if (rank[i] < rank[j]) id[i] = j;
    else {
      id[j] = i;
      if (rank[i] == rank[j]) rank[j]++;
    }
    --cnt;
  }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        UnionFind uf(edges.size());
        for (auto e : edges) {
            if (uf.connected(e[0] - 1, e[1] - 1)) return e;
            uf.connect(e[0] - 1, e[1] - 1);
        }
    }
};

class Solution:
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        tree = [-1] * (len(edges) + 1)
        for edge in edges:
            a = self.findRoot(edge[0], tree)
            b = self.findRoot(edge[1], tree)
            if a != b:
                tree[a] = b
            else:
                return edge
        
        
    def findRoot(self, x, tree):
        if tree[x] == -1: return x
        else:
            root = self.findRoot(tree[x], tree)
            tree[x] = root
            return root

684 - Redundant Connection

All Problems

All Solutions