redundant_connection
1# @leet start 2class Solution: 3 def findRedundantConnection(self, edges: list[list[int]]) -> list[int]: 4 """ 5 To find the redundant connection, we can use Union-Find. 6 Union-Find creates groups of nodes where any node can reach any other 7 node in the group. If the nodes in an edge already belong to a group, 8 it's a redundant connection, because we can remove said edge and 9 still reach every other node. 10 11 So, `find` is set up as normal, where it recursively tries to find 12 the parent of the provided node, `x`, and returns when it finds it. 13 14 `union` joins two groups together. It finds the parents of both nodes, 15 and if their parents are the same, they're already in the same group, so it 16 does nothing. If not, it sets one of the nodes to be parent of the other. 17 18 We can use this property of `union` and exploit it -- if two nodes 19 are in the same group, the edge connecting them is redundant, so we 20 can return that edge. 21 22 For union, if the nodes have the same parent, we return True, and 23 otherwise, return False. We can then detect a redundant connection in 24 a graph. 25 26 The final thing to do is to traverse the whole graph and return the answer. 27 """ 28 n = len(edges) 29 parents = {i: i for i in range(n + 1)} 30 31 def find(x): 32 if parents[x] != x: 33 parents[x] = find(parents[x]) 34 return parents[x] 35 36 def union(x, y): 37 par_x, par_y = find(x), find(y) 38 if par_x != par_y: 39 parents[par_x] = par_y 40 return par_x != par_y 41 42 for u, v in edges: 43 if not union(u, v): 44 return [u, v] 45 46 # unreachable due to the problem statement 47 return [-1, -1] 48 49 50# @leet end 51 52 53def test(): 54 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def findRedundantConnection(self, edges: list[list[int]]) -> list[int]: 5 """ 6 To find the redundant connection, we can use Union-Find. 7 Union-Find creates groups of nodes where any node can reach any other 8 node in the group. If the nodes in an edge already belong to a group, 9 it's a redundant connection, because we can remove said edge and 10 still reach every other node. 11 12 So, `find` is set up as normal, where it recursively tries to find 13 the parent of the provided node, `x`, and returns when it finds it. 14 15 `union` joins two groups together. It finds the parents of both nodes, 16 and if their parents are the same, they're already in the same group, so it 17 does nothing. If not, it sets one of the nodes to be parent of the other. 18 19 We can use this property of `union` and exploit it -- if two nodes 20 are in the same group, the edge connecting them is redundant, so we 21 can return that edge. 22 23 For union, if the nodes have the same parent, we return True, and 24 otherwise, return False. We can then detect a redundant connection in 25 a graph. 26 27 The final thing to do is to traverse the whole graph and return the answer. 28 """ 29 n = len(edges) 30 parents = {i: i for i in range(n + 1)} 31 32 def find(x): 33 if parents[x] != x: 34 parents[x] = find(parents[x]) 35 return parents[x] 36 37 def union(x, y): 38 par_x, par_y = find(x), find(y) 39 if par_x != par_y: 40 parents[par_x] = par_y 41 return par_x != par_y 42 43 for u, v in edges: 44 if not union(u, v): 45 return [u, v] 46 47 # unreachable due to the problem statement 48 return [-1, -1]
def
findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
4 def findRedundantConnection(self, edges: list[list[int]]) -> list[int]: 5 """ 6 To find the redundant connection, we can use Union-Find. 7 Union-Find creates groups of nodes where any node can reach any other 8 node in the group. If the nodes in an edge already belong to a group, 9 it's a redundant connection, because we can remove said edge and 10 still reach every other node. 11 12 So, `find` is set up as normal, where it recursively tries to find 13 the parent of the provided node, `x`, and returns when it finds it. 14 15 `union` joins two groups together. It finds the parents of both nodes, 16 and if their parents are the same, they're already in the same group, so it 17 does nothing. If not, it sets one of the nodes to be parent of the other. 18 19 We can use this property of `union` and exploit it -- if two nodes 20 are in the same group, the edge connecting them is redundant, so we 21 can return that edge. 22 23 For union, if the nodes have the same parent, we return True, and 24 otherwise, return False. We can then detect a redundant connection in 25 a graph. 26 27 The final thing to do is to traverse the whole graph and return the answer. 28 """ 29 n = len(edges) 30 parents = {i: i for i in range(n + 1)} 31 32 def find(x): 33 if parents[x] != x: 34 parents[x] = find(parents[x]) 35 return parents[x] 36 37 def union(x, y): 38 par_x, par_y = find(x), find(y) 39 if par_x != par_y: 40 parents[par_x] = par_y 41 return par_x != par_y 42 43 for u, v in edges: 44 if not union(u, v): 45 return [u, v] 46 47 # unreachable due to the problem statement 48 return [-1, -1]
To find the redundant connection, we can use Union-Find. Union-Find creates groups of nodes where any node can reach any other node in the group. If the nodes in an edge already belong to a group, it's a redundant connection, because we can remove said edge and still reach every other node.
So, find is set up as normal, where it recursively tries to find
the parent of the provided node, x, and returns when it finds it.
union joins two groups together. It finds the parents of both nodes,
and if their parents are the same, they're already in the same group, so it
does nothing. If not, it sets one of the nodes to be parent of the other.
We can use this property of union and exploit it -- if two nodes
are in the same group, the edge connecting them is redundant, so we
can return that edge.
For union, if the nodes have the same parent, we return True, and otherwise, return False. We can then detect a redundant connection in a graph.
The final thing to do is to traverse the whole graph and return the answer.
def
test():