Union Find

In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal’s algorithm for finding the minimum spanning tree of a graph.

Redundant Connection

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 Example 1: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: looks like: 1 /
2 - 3 Example 2: Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: looks like: 5 - 1 - 2 | | 4 - 3 Notice 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.

class Solution:
    """
    @param edges: List[List[int]]
    @return: List[int]
    """
    def findRedundantConnection(self, edges):
        # write your code here
        def is_connected(arr, i, j):
            if parent(arr, i) == parent(arr, j): return True
            return False
            
        def parent(arr, i):
            while i != arr[i]:
                i = arr[i]
            return i
                    
        def union(arr, i, j):
            iroot = parent(arr, i)
            jroot = parent(arr, j)
            if iroot == jroot: return
            arr[iroot] = jroot
            
        _max = list(sorted([i for pair in edges for i in pair]))[-1]
        
        data = [i for i in range(0, _max+1)]

        for i, j in edges:
            if is_connected(data, i, j):
                return [i,j]
            else:
                union(data, i, j)

Tags

• Algorithm