Redundant Connection II Python Solution

Tested Python solution for LeetCode 685 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 685, Hard. Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 685   # by problem number
lcpy gen -s redundant_connection_ii   # by problem name

​

Problem

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u_i, v_i] that represents a directed edge connecting nodes u_i and v_i, where u_i is a parent of child v_i.

Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

​

Examples

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]

​

Constraints

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= u_i, v_i <= n
• u_i != v_i

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n * alpha(n))
    # Space: O(n)
    def find_redundant_directed_connection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = list(range(n + 1))
        dsu = list(range(n + 1))
        candidate_first: list[int] | None = None
        candidate_last: list[int] | None = None
        cycle_edge: list[int] | None = None

        def find(node: int) -> int:
            while dsu[node] != node:
                dsu[node] = dsu[dsu[node]]
                node = dsu[node]
            return node

        for u, v in edges:
            if parent[v] != v:
                candidate_first = [parent[v], v]
                candidate_last = [u, v]
                continue
            parent[v] = u
            root_u, root_v = find(u), find(v)
            if root_u == root_v:
                cycle_edge = [u, v]
            else:
                dsu[root_u] = root_v

        if candidate_first is None:
            assert cycle_edge is not None
            return cycle_edge
        if cycle_edge is not None:
            return candidate_first
        assert candidate_last is not None
        return candidate_last

​

Complexity

Time	Space
O(n * alpha(n))	O(n)

​

Tags