Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

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

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

class Solution {
    private $seen;
    private $MAX_EDGE_VAL = 1000;

    function findRedundantConnection($edges) {
        $graph = array_fill(0, $this->MAX_EDGE_VAL + 1, []);

        foreach ($edges as $edge) {
            $this->seen = [];
            if (!empty($graph[$edge[0]]) && !empty($graph[$edge[1]]) &&
                $this->dfs($graph, $edge[0], $edge[1])) {
                return $edge;
            }
            $graph[$edge[0]][] = $edge[1];
            $graph[$edge[1]][] = $edge[0];
        }
        throw new Exception("No redundant connection found");
    }

    function dfs($graph, $source, $target) {
        if (!in_array($source, $this->seen)) {
            $this->seen[] = $source;
            if ($source == $target) return true;
            foreach ($graph[$source] as $nei) {
                if ($this->dfs($graph, $nei, $target)) return true;
            }
        }
        return false;
    }
}

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