Redundant Connection - Leetcode Solution

The Redundant Connection problem on LeetCode is a graph problem. The problem statement is as follows:

In a directed graph with n nodes labeled 1 to n, there exists an edge connecting nodes u and v such that u != v and the edge is not already in the graph. We say the edge (u, v) is a redundant connection if and only if there is a path from node u to node v or if there is a path from node v to node u in the graph. Return an edge that can be 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 given 2D-array. The answer edge (u, v) should be in the same format, with u and v being integers between 1 and n.

Example: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like below: 1 /
2 - 3 The edge [2,3] is creating a cycle, so it is removed.

Solution:

To solve this problem, we can use union-find algorithm. We can initialize a parent array with values from 1 to n. We can also initialize a rank array with values 0. Next, we can iterate through each edge in the given input edges. For each edge, we can check if the nodes u and v belong to the same set. If they do, that means adding this edge will create a cycle. So, we can return this edge as the answer. If they don't belong to the same set, we can merge the two sets and update the rank array accordingly. We can implement union-find algorithm as follows:

def find(parent, i): if parent[i] == i: return i return find(parent, parent[i])

def union(parent, rank, x, y): xroot = find(parent, x) yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
    parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
    parent[yroot] = xroot
else:
    parent[yroot] = xroot
    rank[xroot] += 1

Once we have merged the two sets, we can repeat the same process for the next edge in the input edges. If we don't find any cycle after iterating through all the edges, that means the given graph is already a tree and we can return the last edge as the answer.

Here's the complete code:

def find(parent, i): if parent[i] == i: return i return find(parent, parent[i])

def union(parent, rank, x, y): xroot = find(parent, x) yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
    parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
    parent[yroot] = xroot
else:
    parent[yroot] = xroot
    rank[xroot] += 1

class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: n = len(edges) parent = [i for i in range(n+1)] rank = [0 for i in range(n+1)]

    for edge in edges:
        u = edge[0]
        v = edge[1]

        if find(parent, u) == find(parent, v):
            return edge

        union(parent, rank, u, v)

    return [-1, -1]

Time Complexity: O(n * alpha(n)) = O(n), where alpha(n) is the inverse Ackermann function which has a very slow growth rate and can be considered as a constant for practical purposes. Space Complexity: O(n), for parent and rank arrays.

Thus, we have solved the Redundant Connection problem on LeetCode.

1