Using Bridges and Articulation Points | Explained
While it\'s a lesser known topic than Union Find and DFS, this can actually be modelled perfectly by Tarjan\'s Bridge finding algorithm.\nWe capture low and dis
While it\'s a lesser known topic than Union Find and DFS, this can actually be modelled perfectly by Tarjan\'s Bridge finding algorithm.\nWe capture low and disc for each node in the traversal, and then we check if any of them are a bridge.\n\nIn this question, we need to find the last edge which is *not* a bridge. I had to add an awkward bit of swap logic since I\'m checking for bridges after the fact, but otherwise this is a classic implementation of the Bridge finding algorithm.\n\n```\nclass Solution {\n    \n    int time = 1;\n    public int[] findRedundantConnection(int[][] edges) {\n\n        int n = edges.length;\n        int[] low = new int[n + 1];\n        int[] disc = new int[n + 1];\n        \n        List<List<Integer>> adjList = buildGraph(edges);\n        dfs(adjList, 1, low, disc, -1);\n        \n        for (int i = n - 1; i >= 0; i--) {\n            int[] edge = edges[i];\n            int u = edge[0];\n            int v = edge[1];\n            \n            // Swap since u must always be the earlier node during our check\n            if (disc[u] > disc[v]) {\n                int temp = u;\n                u = v;\n                v = temp;\n            }\n            \n            if (low[v] > disc[u]){\n                // We have bridge\n                continue;\n            } else {\n                return edge;\n            }\n        }\n        \n        return null;\n    }\n    \n    private List<List<Integer>> buildGraph(int[][] edges) {\n        int n = edges.length;\n        List<List<Integer>> adjList = new ArrayList<>();\n        for (int i = 0; i <= n; i++) {\n            adjList.add(new ArrayList<>());\n        }\n        \n        for (int[] edge: edges) {\n            int src = edge[0];\n            int dst = edge[1];\n            adjList.get(src).add(dst);\n            adjList.get(dst).add(src);\n        }\n        \n        return adjList;\n    }\n    \n    private void dfs(List<List<Integer>> adjList, int u, int[] low, int[] disc, int parent) {\n        if (disc[u] != 0) {\n            return;\n        }\n        \n        disc[u] = time;\n        low[u] = time;\n        time++;\n        \n        for (int v: adjList.get(u)) {\n            if (v == parent) {\n                continue;\n            }\n            if (disc[v] == 0) {\n                dfs(adjList, v, low, disc, u);\n                low[u] = Math.min(low[u], low[v]);\n            } else {\n                low[u] = Math.min(low[u], disc[v]);\n            }\n        }\n    }\n}\n```\n
['Java']