Задача: 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⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    HashSet<int> seen = new HashSet<int>();
    const int MAX_EDGE_VAL = 1000;

    public int[] FindRedundantConnection(int[][] edges) {
        List<int>[] graph = new List<int>[MAX_EDGE_VAL + 1];
        for (int i = 0; i <= MAX_EDGE_VAL; i++) {
            graph[i] = new List<int>();
        }

        foreach (var edge in edges) {
            seen.Clear();
            if (graph[edge[0]].Count > 0 && graph[edge[1]].Count > 0 &&
                    Dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        throw new InvalidOperationException("No redundant connection found");
    }

    public bool Dfs(List<int>[] graph, int source, int target) {
        if (!seen.Contains(source)) {
            seen.Add(source);
            if (source == target) return true;
            foreach (int nei in graph[source]) {
                if (Dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
}

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