685. Redundant Connection II

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ᵢ, vᵢ] that represents a directed edge connecting nodes uᵢ and vᵢ, where uᵢ is a parent of child vᵢ.

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.

https://leetcode.com/problems/redundant-connection-ii/

Example 1:

case1

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

Example 2:

case2

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ᵢ, vᵢ <= n
uᵢ != vᵢ

Test Cases

1 2	class Solution: def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('edges, expected', [
    ([[1,2],[1,3],[2,3]], [2,3]),
    ([[1,2],[2,3],[3,4],[4,1],[1,5]], [4,1]),

    ([[2,1],[3,1],[4,2],[1,4]], [2,1]),
    ([[5,2],[5,1],[3,1],[3,4],[3,5]], [3,1]),

    ([[4,1],[1,5],[4,2],[5,1],[4,3]], [5,1]),
    ([[3,4],[4,1],[1,2],[2,3],[5,1]], [4,1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, edges, expected):
    assert sol.findRedundantDirectedConnection(edges) == expected

Thoughts

684. Redundant Connection 的进阶版，从无向图变为有向图。

如果忽略边的方向，冗余的边依然会导致图中出现环，但在有向图中并不是任何一条边都可以被删掉。比如 edges = [[2,1], [3,1], [4,2], [1,4]]，环 1 → 4 → 2 → 1 上的边 (1, 4) 和 (4, 2) 都不是冗余的。

在有向图中，冗余的边可能会导致某个节点的入度为 2（如 Example 1 和上边的 case）。这种情况下，冗余边一定是两条入边中的某一条。显然这两条入边，一定有一条在（忽略边方向的）环上，而另一条不在。把在环上的那条删掉就行。关键在于如果判断哪条边在环上。

先找入度为 2 的节点。只需要遍历所有的边，记录每个节点的父节点，找到有两个父节点的节点。对应的两条入边，按遇到的先后顺序，记为 e1 和 e2。

有可能不存在入度为 2 的节点，那么直接忽略边的方向，利用并查集（disjoint set）找到图中的环，产生环的最后一条边就是所求的冗余边。

如果存在入度为 2 的节点，可以先假设其中一条入边不存在（不妨假设 e2 不存在），尝试在图中找环。如果没找到环，说明 e2 就在环上，它就是所求的冗余边。如果能找到环，说明 e2 本就不在环上，那么 e1 一定在环上，e1 是所求的冗余边。

Code

solution.py

class DisjointSet:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n)) # parent[u]: u's parent node.
        self.depth = [0] * n # depth[u]: the max depth starting from u.

    def find(self, u: int) -> int:
        while self.parent[u] != u: u = self.parent[u]
        return u

    def union(self, u: int, v: int) -> bool:
        ur = self.find(u)
        vr = self.find(v)
        if ur == vr: return False

        if (diff := self.depth[ur] - self.depth[vr]) == 0:
            self.depth[ur] += 1
        elif diff < 0:
            ur, vr = vr, ur # Make sure that depth[ur] >= depth[vr]

        self.parent[vr] = ur
        return True


class Solution:
    def findRedundantDirectedConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)

        bad = None
        parents: dict[int, int] = {} # v: u, where (u, v) is an edge.
        for e in edges:
            if e[1] in parents:
                bad = e
                break
            parents[e[1]] = e[0]

        loop = None
        disjoint = DisjointSet(n)
        for e in edges:
            if e == bad: continue # Important!
            if not disjoint.union(e[0] - 1, e[1] - 1):
                loop = e
                break

        if not loop:
            return bad
        elif not bad:
            return loop
        else:
            return [parents[bad[1]], bad[1]]

本文引用
- 684. Redundant Connection

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。