JAVA || Time : O(E log E) Space : O(E+V) || Kruskal's || Explanation || Faster than 90%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding both critical and pseudo-critical edges in a given weighte
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding both critical and pseudo-critical edges in a given weighted undirected connected graph\'s minimum spanning tree (MST). A critical edge is an MST edge whose removal increases the MST weight, while a pseudo-critical edge can exist in some but not all MSTs. We can solve this problem by first building the MST using Kruskal\'s algorithm and then identifying the critical and pseudo-critical edges based on certain conditions.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Construct the initial graph using the given edges, where `graph[from][to][0]` stores the edge weight and `graph[from][to][1]` stores the edge index.\n2. Sort the edges in ascending order of their weights.\n3. Build the MST using Kruskal\'s algorithm while tracking the included edges using `mstEdgeSet`.\n4. During the MST construction, store the minimum spanning tree\'s structure in the `minimumSpanningTree` array.\n5. For each edge not included in the MST, check if it is a pseudo-critical edge by verifying if there exists a path between its endpoints with the same weight as the edge being considered.\n6. Identify the critical edges by examining the edges present in the MST but not classified as pseudo-critical.\n7. Return the lists of critical and pseudo-critical edges.\n\n# Complexity\n- Time complexity: O(E * log E) due to the sorting of edges and the MST construction. Here, E is the number of edges in the graph.\n\n- Space complexity: O(E + V) for the graph storage, where V is the number of vertices in the graph.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        int[][][] graph = new int[n][n][2]; // {weight, index}\n        for (int i = 0; i < edges.length; i++) {\n            int[] edge = edges[i];\n            int from = edge[0];\n            int to = edge[1];\n            int weight = edge[2];\n            graph[from][to][0] = weight;\n            graph[to][from][0] = weight;\n            graph[from][to][1] = i;\n            graph[to][from][1] = i;\n        }\n\n        List<Integer>[] minimumSpanningTree = new List[n];\n        for (int i = 0; i < n; i++) {\n            minimumSpanningTree[i] = new LinkedList<>();\n        }\n\n        boolean[] mstEdgeSet = new boolean[edges.length];\n\n        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));\n\n        buildMinimumSpanningTree(n, edges, mstEdgeSet, minimumSpanningTree, graph);\n\n        List<List<Integer>> result = new ArrayList<>(2);\n        Set<Integer> pseudoCriticalEdges = new HashSet<>();\n        List<Integer> criticalEdges = new LinkedList<>();\n\n        // Finding pseudo-critical edges\n        for (int i = 0; i < edges.length; i++) {\n            int from = edges[i][0], to = edges[i][1];\n            int weight = edges[i][2];\n            int index = graph[from][to][1];\n            if (!mstEdgeSet[index]) {\n                Set<Integer> currentSet = new HashSet<>();\n                boolean isPseudoCritical = isPath(from, to, weight, -1, minimumSpanningTree, graph, currentSet);\n                if (isPseudoCritical && currentSet.size() > 0) {\n                    pseudoCriticalEdges.addAll(currentSet);\n                    pseudoCriticalEdges.add(index);\n                }\n            }\n        }\n\n        // Finding critical edges\n        for (int i = 0; i < edges.length; i++) {\n            int from = edges[i][0], to = edges[i][1];\n            int index = graph[from][to][1];\n            if (mstEdgeSet[index] && !pseudoCriticalEdges.contains(index)) {\n                criticalEdges.add(index);\n            }\n        }\n\n        result.add(criticalEdges);\n        result.add(new LinkedList<>(pseudoCriticalEdges));\n        return result;\n    }\n\n    boolean isPath(int from, int to, int weight, int previous, List<Integer>[] minimumSpanningTree, int[][][] graph, Set<Integer> indices) {\n        if (from == to) {\n            return true;\n        }\n        for (int neighbor : minimumSpanningTree[from]) {\n            if (previous != neighbor) {\n                if (isPath(neighbor, to, weight, from, minimumSpanningTree, graph, indices)) {\n                    if (graph[from][neighbor][0] == weight) {\n                        indices.add(graph[from][neighbor][1]);\n                    }\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\n    private void buildMinimumSpanningTree(int n, int[][] edges, boolean[] mstEdgeSet, List<Integer>[] minimumSpanningTree, int[][][] graph) {\n        int weight = 0;\n        DisjointSet ds = new DisjointSet(n);\n\n        for (int i = 0; i < edges.length; i++) {\n            if (ds.union(edges[i][0], edges[i][1])) {\n                weight += edges[i][2];\n                int[] edge = edges[i];\n                minimumSpanningTree[edge[0]].add(edge[1]);\n                minimumSpanningTree[edge[1]].add(edge[0]);\n                mstEdgeSet[graph[edge[0]][edge[1]][1]] = true;\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```
['Tree', 'Minimum Spanning Tree', 'Java']