[Java] Intuitive Solution using Prim's and Graph Partitions, with Detailed Explanation (O(EV))
Honestly this was kind of nasty to implement but hey it works and makes sense. \n\nStep 1: Generate an MST (using standard Prim\'s algorithm).\nStep 2: For ever
Honestly this was kind of nasty to implement but hey it works and makes sense. \n\nStep 1: Generate an MST (using standard Prim\'s algorithm).\nStep 2: For every edge in the MST: consider the cut formed by removing (only) this edge e of weight w from the MST. For all edges in the original graph crossing this e-induced cut, we have that any such edge that also has weight w and was not in our formed MST from Step 1 can be added to the cut to create a new MST (with the same weight as our initial MST). If there is more than one edge satisfying this criteria (so an edge besides just e), then all such edges are pseudo-critical. Else e is a critical edge.\n\n```\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<Set<int[]>> G = new ArrayList();\n        for (int i = 0; i < n; i++) G.add(new HashSet());\n        for (int i = 0; i < edges.length; i++) {\n            int[] e = edges[i];\n            G.get(e[0]).add(new int[]{e[1], e[2], i});\n            G.get(e[1]).add(new int[]{e[0], e[2], i});\n        }\n        Set<Integer> V = new HashSet();\n        V.add(0);\n        PriorityQueue<int[]> PQ = new PriorityQueue<>((a,b) -> Integer.compare(a[1], b[1]));\n        PQ.addAll(G.get(0));\n        List<Integer> MST = new ArrayList();\n        while (!PQ.isEmpty()) {\n            while (!PQ.isEmpty() && V.contains(PQ.peek()[0])) PQ.poll();\n            if (PQ.isEmpty()) break;\n            int[] top = PQ.poll();\n            MST.add(top[2]);\n            V.add(top[0]);\n            for (int[] e : G.get(top[0]))\n                if (!V.contains(e[0])) PQ.add(e);\n        }\n        int[][] mstEdges = new int[MST.size()][3];\n        for (int i = 0; i < MST.size(); i++) mstEdges[i] = edges[MST.get(i)];\n        Set<Integer> criticals = new HashSet(), pseudos = new HashSet();\n        for (int i = 0; i < mstEdges.length; i++) {\n            List<Set<Integer>> partition = genCut(mstEdges, n, i);\n            Set<Integer> P1 = partition.get(0), P2 = partition.get(1);\n            int w = mstEdges[i][2];\n            Set<Integer> mins = new HashSet();\n            mins.add(MST.get(i));\n            for (int u : P1) \n                for (int[] e : G.get(u)) \n                    if (P2.contains(e[0]) && e[1] == w) {\n                        mins.add(e[2]);\n                    }\n            if (mins.size() > 1) pseudos.addAll(mins);\n            else criticals.addAll(mins);\n        }\n        return Arrays.asList(new ArrayList(criticals), new ArrayList(pseudos));\n    }\n    \n    private List<Set<Integer>> genCut(int[][] E, int n, int removeIdx) {\n        List<Set<Integer>> G = new ArrayList();\n        for (int i = 0; i < n; i++) G.add(new HashSet());\n        for (int i = 0; i < E.length; i++) {\n            if (i == removeIdx) continue;\n            int[] e = E[i];\n            G.get(e[0]).add(e[1]);\n            G.get(e[1]).add(e[0]);\n        }\n        Set<Integer> S1 = new HashSet();\n        S1.add(0);\n        dfs(0, G, S1);\n        int idx2 = 1;\n        for (int i = 1; i < n; i++) {\n            if (!S1.contains(i)) {\n                idx2 = i;\n                break;\n            }\n        }\n        Set<Integer> S2 = new HashSet();\n        S2.add(idx2);\n        dfs(idx2, G, S2);\n        return Arrays.asList(S1, S2);\n    }\n    \n    private void dfs(int u, List<Set<Integer>> G, Set<Integer> V) {\n        for (int v : G.get(u))\n            if (!V.contains(v)) {\n                V.add(v);\n                dfs(v, G, V);\n            }\n    }\n}\n```
[]