Задача: 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 {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        unordered_map<int, int> parent;
        vector<vector<int>> candidates;
        for (auto& edge : edges) {
            if (parent.count(edge[1])) {
                candidates.push_back({parent[edge[1]], edge[1]});
                candidates.push_back(edge);
            } else {
                parent[edge[1]] = edge[0];
            }
        }

        int root = orbit(1, parent).node;
        if (candidates.empty()) {
            auto cycle = orbit(root, parent).seen;
            vector<int> ans = {0, 0};
            for (auto& edge : edges) {
                if (cycle.count(edge[0]) && cycle.count(edge[1])) {
                    ans = edge;
                }
            }
            return ans;
        }

        unordered_map<int, vector<int>> children;
        for (auto& p : parent) {
            children[p.second].push_back(p.first);
        }

        vector<bool> seen(N + 1, false);
        seen[0] = true;
        stack<int> stk;
        stk.push(root);
        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            if (!seen[node]) {
                seen[node] = true;
                for (int c : children[node]) {
                    stk.push(c);
                }
            }
        }
        for (bool b : seen) {
            if (!b) {
                return candidates[0];
            }
        }
        return candidates[1];
    }

private:
    struct OrbitResult {
        int node;
        unordered_set<int> seen;
        OrbitResult(int n, unordered_set<int> s) : node(n), seen(s) {}
    };

    OrbitResult orbit(int node, unordered_map<int, int>& parent) {
        unordered_set<int> seen;
        while (parent.count(node) && !seen.count(node)) {
            seen.insert(node);
            node = parent[node];
        }
        return OrbitResult(node, seen);
    }
};

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