diff options
Diffstat (limited to 'redundant_connection.py')
-rw-r--r-- | redundant_connection.py | 52 |
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]])) |