100% faster, O(EV): Building MST once is enough.
\n Following 4 steps are required in algo.\n \n1. Create graph as adjacency matrix of int[][][] type and keep edge weight and indices in the matrix. Indices are
\n Following 4 steps are required in algo.\n \n1. Create graph as adjacency matrix of `int[][][]` type and keep edge weight and indices in the matrix. Indices are kept so that we don\'t loose track of indices while sorting edges in Kruskal\'s algo\n2. Create MST using Kruskal\'s algo on our graph created in step 1. Store this tree in new adjacency list(variable `mst` in code) and also the set of edges Indices used to create MST(variable `mstSet`)\n3. For each edge `(u,v)` not in MST, if there exist edge `(x,y)` in MST on path from u to v such that `cost(u,v) = cost(x,y)` then `u,v` is a psuedo critical edge\n4. For each edge `(u,v)` in MST, if it is not a psuedo critical edge, then it\'s a critical edge.\n\n\nPlease check https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/14/Small14.pdf.\nThere is proof of prim\'s algo(also applicable for kruskal\'s algo) in this pdf, which can help understand the validity of step 3 and step 4.\n\n**Intuition behind step 3**: Let\'s say path from u to v is denoted by  `P(u,v)` in MST. For any two vertices `u` and `v` there exists one and only path  `P(u,v)` in MST because MST is one connected tree covering all n vertices with n-1 edges. Therefore, adding any edge  `(u,v)` not in MST to MST will create one cycle .  If `(x,y)` is in `P(u,v)` in MST such that `cost(u,v) = cost(x,y)`, and if we remove `(x,y)`  from MST and add `(u,v)` to MST, our cost of MST will remain same because we are deleting and adding same weight edge, and the cycle created by adding edge `(u,v)` to MST will break after we remove edge `x,y`, which will create new MST implying that edge `(u,v)` was psuedo critical.\n\n\n**Intuition behind step 4**: All edges in MST except psuedo critical edges were the minimum edges that we found during our algo, if we try to delete it, then the total weight cost of MST will only increase because there is no edge of the same(if such exist, it could be psuedo-critical) or less weight in non-MST which could have been added during algo run.\n\nTime Complexity: \nTime complexity of Kruskal = O(ELogE + ELogV)\nTime complexity to find psuedo critical edges = O(E(E\'+V)) where E\' are no. of edges in MST. \nWe are running `path` on MST which is tree, therefore E\' = V-1\nHence, Time complexity to find psuedo critical edges = O(EV)\nTime complexity to find critical edges = O(E)\n\nTotal time complexity = O(EV)\n\n```\nclass Solution {\n\tpublic List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n\t\tint[][][] g = new int[n][n][2]; //{w,ind}\n\t\tfor(int i = 0; i < edges.length; i ++) {\n\t\t\tint[] e = edges[i];\n\t\t\tint f = e[0];\n\t\t\tint t = e[1];\n\t\t\tint w = e[2];\n\t\t\tg[f][t][0] = w;\n\t\t\tg[t][f][0] = w;\n\t\t\tg[f][t][1] = i;\n\t\t\tg[t][f][1] = i;\n\t\t}\n\n\t\tList<Integer>[] mst = new List[n];\n\t\tfor(int i = 0; i < n; i ++) {\n\t\t\tmst[i] = new LinkedList<>();\n\t\t}\n\n\t\tboolean[] mstSet = new boolean[edges.length];\n\n        Arrays.sort(edges, (a,b) -> Integer.compare(a[2], b[2]));\n        \n        buildMST(n, edges, mstSet, mst, g);\n\t\t\n\t\tList<List<Integer>> ans = new ArrayList<>(2);\n\t\tSet<Integer> pce = new HashSet<>();\n\t\tList<Integer> ce = new LinkedList<>();\n\t\t\n\t\t// psuedo critical edges\n\t\tfor(int i = 0; i < edges.length; i ++) {\n            int f = edges[i][0], t = edges[i][1];\n            int w = edges[i][2];\n            int ind = g[f][t][1];\n\t\t\tif(!mstSet[ind]) {\n                Set<Integer> cur = new HashSet<>();\n\t\t\t\tboolean p = path(f, t, w, -1, mst, g, cur);\n                if(p && cur.size() > 0) {\n                    pce.addAll(cur);\n                    pce.add(ind);\n                }\n\t\t\t\tif(!p) {\n\t\t\t\t\tSystem.out.println("Should not reach here");\n\t\t\t\t}\n\t\t\t}\n\t\t\t\n\t\t}\n\n\t\t// critical edges\n\t\tfor(int i = 0; i < edges.length; i ++) {\n            int f = edges[i][0], t = edges[i][1];\n            int w = edges[i][2];\n            int ind = g[f][t][1];\n\t\t\tif(mstSet[ind] && !pce.contains(ind)) {\n\t\t\t\tce.add(ind);\n\t\t\t}\n\t\t}\n\t\t\n\t\t\n\t\tans.add(ce);\n\t\tans.add(new LinkedList<>(pce));\n\t\treturn ans;\n\n\t}\n\n\tboolean path(int f, int t, int w, int p, List<Integer>[] mst, int[][][] g, Set<Integer> ind) {\n\t\tif(f == t) {\n\t\t\treturn true; \n\t\t}\n\t\tfor(int nbr: mst[f]) {\n\t\t\tif(p != nbr) {\n\t\t\t\t\n\t\t\t\tif(path(nbr, t, w, f, mst, g, ind)) {\n\t\t\t\t\tif(g[f][nbr][0] == w) {\n\t\t\t\t\t\tind.add(g[f][nbr][1]);\n\t\t\t\t\t}\n\t\t\t\t\treturn true;\n\t\t\t\t}\n\t\t\t\t\n\t\t\t}\n\t\t}\n\t\treturn false;\n\t}\n    \n    private void buildMST(int n, int[][] edges, boolean[] mste, List<Integer>[] mstg, int[][][] g){\n        int weight = 0; \n        DisjointSet ds = new DisjointSet(n);\n        \n        for (int i = 0; i < edges.length; i++) {\n            \n            if (ds.union(edges[i][0], edges[i][1])) {\n                weight += edges[i][2];\n                int[] edge = edges[i];\n                mstg[edge[0]].add(edge[1]);\n                mstg[edge[1]].add(edge[0]);\n                mste[g[edge[0]][edge[1]][1]] = true;\n            }\n        }\n    }\n}\n\n\nclass DisjointSet {\n    int[] parent;\n    \n    public DisjointSet(int n) {\n        parent = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n    }\n    \n    public int find(int i) {\n        return (i == parent[i]) ? i : (parent[i] = find(parent[i]));\n    }\n    \n    public boolean union(int u, int v) {\n        int pu = find(u), pv = find(v);\n        if (pu == pv) {\n            return false;\n        }\n        parent[pu] = pv;\n        return true;\n    }\n}\n```\n\n![image](https://assets.leetcode.com/users/images/4835adfa-b31c-41de-ba03-54ffca957375_1632319257.3089685.png)\n
['Depth-First Search', 'Java']