LeetCode/cs/redundant-connection.cs

public class Solution {
    private List<int>[] MakeGraph(int n, int[][] edges) {
        var g = new List<int>[n];
        for (var i = 0; i < n; ++i) {
            g[i] = [];
        }

        foreach (var edge in edges) {
            var (u, v) = (edge[0] - 1, edge[1] - 1);
            g[u].Add(v);
            g[v].Add(u);
        }

        return g;
    }

    private class DFS {
        private readonly List<int>[] g;

        private readonly bool[] visited;
        public bool Visited(int index) => visited[index];

        private readonly int[] parent;
        public int Parent(int index) => parent[index];

        public int CycleStart { get; private set; } = -1;

        public DFS(List<int>[] g) {
            this.g = g;
            visited = new bool[g.Length];

            parent = new int[g.Length];
            Array.Fill(parent, -1);
        }

        public void Run(int u) {
            visited[u] = true;

            foreach (var v in g[u]) {
                if (!visited[v]) {
                    parent[v] = u;
                    Run(v);
                } else if (v != parent[u] && CycleStart == -1) {
                    parent[v] = u;
                    CycleStart = v;
                }
            }
        }
    }

    public int[] FindRedundantConnection(int[][] edges) {
        var n = edges.Length;
        var g = MakeGraph(n, edges);

        var traversal = new DFS(g);
        traversal.Run(0);

        var cycleNodes = new Dictionary<int, int>();

        var node = traversal.CycleStart;
        do {
            cycleNodes[node] = 1;
            node = traversal.Parent(node);
        } while (node != traversal.CycleStart);

        return edges.Reverse().First((edge) => {
            var (u, v) = (edge[0] - 1, edge[1] - 1);
            return cycleNodes.ContainsKey(u) && cycleNodes.ContainsKey(v);
        });
    }
}