Задача: 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 {
    function findRedundantDirectedConnection($edges) {
        $N = count($edges);
        $parent = [];
        $candidates = [];
        foreach ($edges as $edge) {
            if (isset($parent[$edge[1]])) {
                $candidates[] = [$parent[$edge[1]], $edge[1]];
                $candidates[] = $edge;
            } else {
                $parent[$edge[1]] = $edge[0];
            }
        }

        $root = $this->orbit(1, $parent)->node;
        if (empty($candidates)) {
            $cycle = $this->orbit($root, $parent)->seen;
            $ans = [0, 0];
            foreach ($edges as $edge) {
                if (in_array($edge[0], $cycle) && in_array($edge[1], $cycle)) {
                    $ans = $edge;
                }
            }
            return $ans;
        }

        $children = [];
        foreach ($parent as $v => $pv) {
            if (!isset($children[$pv])) {
                $children[$pv] = [];
            }
            $children[$pv][] = $v;
        }

        $seen = array_fill(0, $N + 1, false);
        $seen[0] = true;
        $stack = [$root];
        while (!empty($stack)) {
            $node = array_pop($stack);
            if (!$seen[$node]) {
                $seen[$node] = true;
                if (isset($children[$node])) {
                    foreach ($children[$node] as $c) {
                        $stack[] = $c;
                    }
                }
            }
        }
        foreach ($seen as $b) {
            if (!$b) {
                return $candidates[0];
            }
        }
        return $candidates[1];
    }

    function orbit($node, $parent) {
        $seen = [];
        while (isset($parent[$node]) && !in_array($node, $seen)) {
            $seen[] = $node;
            $node = $parent[$node];
        }
        return (object)[
            'node' => $node,
            'seen' => $seen
        ];
    }
}

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