Create redundant-connection.py

kamyu104 · web-flow · commit d50076b40544 · 2017-09-24T16:54:34.000+08:00
diff --git a/Python/redundant-connection.py b/Python/redundant-connection.py
@@ -0,0 +1,34 @@
+# Time:  O(nlog*n) ~= O(n), n is the length of the positions
+# Space: O(n)
+
+class UnionFind(object):
+    def __init__(self, n):
+        self.set = range(n)
+        self.count = n
+
+    def find_set(self, x):
+       if self.set[x] != x:
+           self.set[x] = self.find_set(self.set[x])  # path compression.
+       return self.set[x]
+
+    def union_set(self, x, y):
+        x_root, y_root = map(self.find_set, (x, y))
+        if x_root == y_root:
+            return False
+        self.set[min(x_root, y_root)] = max(x_root, y_root)
+        self.count -= 1
+        return True
+
+
+class Solution(object):
+    def findRedundantConnection(self, edges):
+        """
+        :type edges: List[List[int]]
+        :rtype: List[int]
+        """
+        union_find = UnionFind(2000)
+        for edge in edges:
+            if not union_find.union_set(*edge):
+                return edge
+        return []
+        
