Задача: 685. Redundant Connection II
Сложность: hard

В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.

Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.

Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.

Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.

Пример:

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

👨‍💻 Алгоритм:

1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.

2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.

3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.

😎 Решение:

class Solution {
    class OrbitResult {
        var node: Int
        var seen: Set<Int>
        init(_ n: Int, _ s: Set<Int>) {
            node = n
            seen = s
        }
    }
    
    func findRedundantDirectedConnection(_ edges: [[Int]]) -> [Int] {
        let N = edges.count
        var parent = [Int: Int]()
        var candidates = [[Int]]()
        
        for edge in edges {
            if let p = parent[edge[1]] {
                candidates.append([p, edge[1]])
                candidates.append(edge)
            } else {
                parent[edge[1]] = edge[0]
            }
        }
        
        let root = orbit(1, parent).node
        if candidates.isEmpty {
            let cycle = orbit(root, parent).seen
            var ans = [0, 0]
            for edge in edges {
                if cycle.contains(edge[0]) && cycle.contains(edge[1]) {
                    ans = edge
                }
            }
            return ans
        }
        
        var children = [Int: [Int]]()
        for (v, pv) in parent {
            children[pv, default: []].append(v)
        }
        
        var seen = [Bool](repeating: false, count: N + 1)
        seen[0] = true
        var stack = [root]
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            if !seen[node] {
                seen[node] = true
                if let childNodes = children[node] {
                    stack.append(contentsOf: childNodes)
                }
            }
        }
        
        for b in seen {
            if !b {
                return candidates[0]
            }
        }
        return candidates[1]
    }
    
    func orbit(_ node: Int, _ parent: [Int: Int]) -> OrbitResult {
        var seen = Set<Int>()
        var node = node
        
        while let next = parent[node], !seen.contains(node) {
            seen.insert(node)
            node = next
        }
        
        return OrbitResult(node, seen)
    }
}

Ставь 👍 и забирай 📚 Базу знаний