Redundant Connection
In this of but saidQuestion is a connection between two nodes. A redundant connection is a connection that, when removed, does not affect the connectivity of the graph. Given a list of connections in a graph, find the redundant connection.
Constraints:
- 1 <= n <= 1000
- n - 1 <= edges.length <= n
- edges[i].length == 2
- 1 <= edges[i][0], edges[i][1] <= n
- edges[i][0] != edges[i][1]
Examples:
Input: [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: The connection between nodes 2 and 3 is redundant because the graph remains connected even if this connection is removed.
Solutions
Union-Find
The Union-Find approach is used to solve this problem. We initialize the parent array where each node is its own parent. Then we iterate over the edges. For each edge, we check if the two nodes are already connected. If they are, we return the edge as it is redundant. Otherwise, we union the two nodes.
def findRedundantConnection(edges):
parent = list(range(len(edges) + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootX = find(x)
rootY = find(y)
if rootX == rootY:
return False
parent[rootX] = rootY
return True
for x, y in edges:
if not union(x, y):
return [x, y]Follow-up:
What if the graph is not connected?
