aboutsummaryrefslogtreecommitdiff
path: root/redundant_connection.py
diff options
context:
space:
mode:
Diffstat (limited to 'redundant_connection.py')
-rw-r--r--redundant_connection.py52
1 files changed, 52 insertions, 0 deletions
diff --git a/redundant_connection.py b/redundant_connection.py
new file mode 100644
index 0000000..665fc5b
--- /dev/null
+++ b/redundant_connection.py
@@ -0,0 +1,52 @@
+# 684. Redundant Connection
+
+"""
+in this problem, a tree is an undirected graph that is connected and has no
+cycles. you are given a graph that started as a tree with 'n' nodes labeled
+from 1 to '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 graph is represented as an array 'edges' of length 'n' where
+'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+and 'b_i' in the graph. return an edge that can 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 input.
+"""
+
+
+class Solution(object):
+ def findRedundantConnection(self, edges):
+ """
+ :type edges: List[List[int]]
+ :rtype: List[int]
+ """
+ parent = [-1] * (len(edges) + 1)
+ rank = [0] * (len(edges) + 1)
+
+ def find(x):
+ if parent[x] == -1:
+ return x
+ parent[x] = find(parent[x])
+ return parent[x]
+
+ def union_set(x, y):
+ root_x, root_y = find(x), find(y)
+ if root_x == root_y:
+ return False
+ elif rank[root_x] < rank[root_y]:
+ parent[root_x] = root_y
+ rank[root_y] += 1
+ return True
+ else:
+ parent[root_y] = root_x
+ rank[root_x] += 1
+ return True
+
+ for x, y in edges:
+ if not union_set(x, y):
+ return [x, y]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findRedundantConnection(edges=[[1, 2], [1, 3], [2, 3]]))
+ print(obj.findRedundantConnection(edges=[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))