Java | Union find | Disjoint set | Kruskal's Algorithm | Clean code
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n### Steps Involved in
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n### Steps Involved in the Algorithm for Finding Critical and Pseudo-Critical Edges in MST\n\n1. **Define Helper Classes**:\n\n   - Create a **Disjoint Set** class to manage union-find operations efficiently.\n   - Define an **Edge** class to represent an edge between two nodes with its weight and index.\n\n2. **Initialize Data Structures**:\n\n   - Convert the given edges into instances of the `Edge` class and store them in a list (`edgeList`).\n   - Sort `edgeList` in ascending order of weights using a comparator. This is essential for Kruskal\'s algorithm.\n\n3. **Find the Minimum Spanning Tree (MST) Weight**:\n\n   - Use **Kruskal\'s algorithm** to find the MST weight.\n   - Start with an empty MST and iterate over the sorted edges, adding edges that do not form a cycle until all nodes are connected.\n   - Store the MST weight as a reference for further comparisons.\n\n4. **Identify Critical Edges**:\n\n   - A **critical edge** is an edge that, if removed, increases the overall weight of the MST or prevents it from forming.\n   - Iterate over each edge and exclude it while calculating the MST weight using the `kruskalsMst()` method.\n   - If excluding an edge increases the MST weight beyond the original MST weight, mark that edge as critical.\n\n5. **Identify Pseudo-Critical Edges**:\n\n   - A **pseudo-critical edge** is an edge that can be part of some MST, but its removal does not necessarily prevent the formation of an MST.\n   - For each edge, force its inclusion in the MST calculation by calling `kruskalsMst()` with the edge included initially.\n   - If the resulting MST weight is the same as the original MST weight, mark the edge as pseudo-critical.\n\n\n\n6. **Return the Results**:\n\n   - Prepare the final result as a list containing two lists: one for **critical** edges and one for **pseudo-critical** edges.\n   - Return this result to provide the categorization of edges in the given graph.\n\n### Complexity Analysis\n\n1. **Time Complexity**:\n\n   - Sorting the edges takes **O(E log E)**, where **E** is the number of edges.\n   - For each edge, we run **Kruskal\'s MST**, which takes **O(E log V)** time using union-find with path compression and union by size, where **V** is the number of vertices.\n   - We repeat the MST calculation for each edge twice (once for exclusion and once for inclusion), resulting in a total time complexity of **O(E \\* (E + V) log V)**.\n\n2. **Space Complexity**:\n\n   - The space complexity is **O(V + E)** due to storing the edges, the disjoint set data structure, and other auxiliary data structures.\n   - The **Disjoint Set** data structure requires **O(V)** space to store the parent and size arrays.\n   - The edge list and other lists used to store the results require **O(E)** space.\n\n### Optimization Improvements\n\n- **Union-Find with Path Compression and Union by Size**: This ensures that the operations for finding and uniting sets are efficient.\n- **Avoiding Redundant Checks**: The connectivity check after building the MST was optimized to use a method (`allConnected()`) that verifies if all nodes are in the same connected component, thus avoiding unnecessary repeated root checks.\n\nThis approach allows us to classify the edges into critical and pseudo-critical categories, leveraging Kruskal\'s MST and efficient disjoint set operations for graph connectivity management.\n\n\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    /**\n     * Disjoint Set (Union-Find) Data Structure\n     */\n    class DisjointSet {\n        int[] size;\n        int[] parent;\n\n        // Constructor to initialize parent and size arrays\n        DisjointSet(int nodeCount) {\n            size = new int[nodeCount + 1];\n            parent = new int[nodeCount + 1];\n\n            // Each node is initially its own parent, and size is 1\n            for (int i = 0; i <= nodeCount; i++) {\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n\n        // Find the ultimate parent of a node with path compression\n        int findUparent(int node) {\n            if (node == parent[node])\n                return node;\n            return parent[node] = findUparent(parent[node]);\n        }\n\n        // Union by size: attach smaller tree under the larger one\n        void unionBySize(int a, int b) {\n            int upa = findUparent(a);\n            int upb = findUparent(b);\n\n            if (upa == upb)\n                return;\n\n            if (size[upa] < size[upb]) {\n                parent[upa] = upb;\n                size[upb] += size[upa];\n            } else {\n                parent[upb] = upa;\n                size[upa] += size[upb];\n            }\n        }\n\n        // Method to check if all nodes are connected\n        boolean allConnected(int n) {\n            int root = findUparent(0);\n            for (int i = 1; i < n; i++) {\n                if (findUparent(i) != root) {\n                    return false;\n                }\n            }\n            return true;\n        }\n    }\n\n    /**\n     * Edge class to represent an edge with two nodes, weight, and index\n     */\n    class Edge {\n        int a;\n        int b;\n        int weight;\n        int index;\n\n        Edge(int a, int b, int weight, int index) {\n            this.a = a;\n            this.b = b;\n            this.weight = weight;\n            this.index = index;\n        }\n    }\n\n    /**\n     * Method to find the Minimum Spanning Tree (MST) weight using Kruskal\'s algorithm\n     * Allows skipping an edge and including a specific edge\n     */\n    int kruskalsMst(List<Edge> edgeList, int skipIndex, int includeIndex, int[][] edges, int n) {\n        DisjointSet ds = new DisjointSet(n);\n        int mstWeight = 0;\n\n        // If an edge is to be forcibly included, add it first\n        if (includeIndex != -1) {\n            int a = edges[includeIndex][0];\n            int b = edges[includeIndex][1];\n            if (ds.findUparent(a) != ds.findUparent(b)) {\n                ds.unionBySize(a, b);\n                mstWeight += edges[includeIndex][2];\n            }\n        }\n\n        // Iterate over all edges to construct MST\n        for (Edge e : edgeList) {\n            // Skip the specified edge\n            if (e.index == skipIndex) continue;\n\n            // Add the edge if it connects two different components\n            if (ds.findUparent(e.a) != ds.findUparent(e.b)) {\n                ds.unionBySize(e.a, e.b);\n                mstWeight += e.weight;\n            }\n        }\n\n        // Verify if all nodes are connected (i.e., form a valid MST)\n        return ds.allConnected(n) ? mstWeight : Integer.MAX_VALUE;\n    }\n\n    /**\n     * Method to find the critical and pseudo-critical edges in the MST\n     */\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<Edge> edgeList = new ArrayList<>();\n\n        int index = 0;\n        for (int[] edge : edges) {\n            edgeList.add(new Edge(edge[0], edge[1], edge[2], index++));\n        }\n\n        // Sort edges by weight in ascending order\n        Collections.sort(edgeList, (a,b) -> Integer.compare(a.weight, b.weight));\n\n        List<Integer> critical = new ArrayList<>();\n        List<Integer> pseudoCritical = new ArrayList<>();\n\n        // Find the weight of the MST without skipping any edges\n        int mstWeight = kruskalsMst(edgeList, -1, -1, edges, n);\n\n        for (Edge edge : edgeList) {\n            // Check if the edge is critical by skipping it\n            int skipEdgeMstWeight = kruskalsMst(edgeList, edge.index, -1, edges, n);\n\n            if (skipEdgeMstWeight > mstWeight) {\n                critical.add(edge.index);\n            } else if (kruskalsMst(edgeList, -1, edge.index, edges, n) == mstWeight) {\n                // Check if the edge is pseudo-critical by including it\n                pseudoCritical.add(edge.index);\n            }\n        }\n\n        // Add critical and pseudo-critical edges to the result\n        List<List<Integer>> result = new ArrayList<>();\n        result.add(critical);\n        result.add(pseudoCritical);\n\n        return result;\n    }\n}\n\n\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Strongly Connected Component', 'Java']