BEGINNER FRIENDLY JAVA CODE | FULLY EXPLAINED
Intuition\nWe are given a graph represented by an array of edges, where each edge has a weight. We want to find critical and pseudo-critical edges in the graph.
# Intuition\nWe are given a graph represented by an array of edges, where each edge has a weight. We want to find critical and pseudo-critical edges in the graph. Critical edges are those that, when removed, increase the overall weight of the minimum spanning tree (MST). Pseudo-critical edges are those that are not critical but become critical when added to the MST. We can solve this problem using Kruskal\'s algorithm for minimum spanning trees.\n\n# Approach\n1. **Disjoint Set Data Structure (`DisjointSet`):** We define a `DisjointSet` class to manage the union-find operations for the graph\'s vertices.\n\n2. **Graph Representation (`Graph`):** We define a `Graph` class to handle the graph\'s representation and operations.\n   - In the constructor, we initialize the sorted edge array `se` and sort it based on the edges\' weights.\n   - We implement three methods:\n     - `kruskal()`: This method implements Kruskal\'s algorithm to find the weight of the MST.\n     - `kruskalInc()`: This method calculates the weight of the MST when an edge is included.\n     - `kruskalExc()`: This method calculates the weight of the MST when an edge is excluded.\n\n3. **Solution (`Solution`):** We define a `Solution` class to solve the problem.\n   - In the `findCriticalAndPseudoCriticalEdges` method, we iterate through each edge and calculate the weight of the MST after including and excluding the edge. Based on these calculations, we determine if the edge is critical or pseudo-critical.\n\n\n**Let\'s go through two examples to understand how the given solution works**\n\n**Example 1:**\n\nConsider the following graph with 4 nodes and 5 edges:\n\n```\n   1\n0 ----- 1\n|\\     |\n| \\3   |4\n|  \\   |\n|   \\  |\n|    \\ |\n2----- 3\n   5\n```\n\nEdges: `[[0, 1, 1], [0, 2, 3], [1, 2, 2], [1, 3, 4], [2, 3, 5]]`\n\nIn this example, we\'ll find the critical and pseudo-critical edges.\n\n1. **Constructing the MST and Initial Weights:**\n   - We use Kruskal\'s algorithm to construct the Minimum Spanning Tree (MST). Initially, all edges are included in the MST with their original weights:\n     - `MST Weight`: 1 + 2 + 3 = 6\n\n2. **Finding Critical Edges:**\n   - For each edge, we calculate the MST weight after excluding it:\n     - For edge `[0, 1, 1]`: MST weight after excluding = 3 + 4 = 7 (increased, so critical)\n     - For edge `[0, 2, 3]`: MST weight after excluding = 1 + 4 = 5 (decreased, not critical)\n     - For edge `[1, 2, 2]`: MST weight after excluding = 1 + 4 = 5 (decreased, not critical)\n     - For edge `[1, 3, 4]`: MST weight after excluding = 3 + 2 = 5 (decreased, not critical)\n     - For edge `[2, 3, 5]`: MST weight after excluding = 3 + 2 = 5 (decreased, not critical)\n   - So, the critical edge is `[0, 1, 1]`.\n\n3. **Finding Pseudo-Critical Edges:**\n   - For each edge, we calculate the MST weight after including it:\n     - For edge `[0, 1, 1]`: MST weight after including = 1 + 2 + 2 + 3 = 8 (increased, not pseudo-critical)\n     - For edge `[0, 2, 3]`: MST weight after including = 1 + 2 + 3 + 4 = 10 (increased, so pseudo-critical)\n     - For edge `[1, 2, 2]`: MST weight after including = 1 + 2 + 2 + 4 = 9 (increased, not pseudo-critical)\n     - For edge `[1, 3, 4]`: MST weight after including = 1 + 2 + 2 + 3 = 8 (increased, not pseudo-critical)\n     - For edge `[2, 3, 5]`: MST weight after including = 1 + 2 + 2 + 3 = 8 (increased, not pseudo-critical)\n   - So, the pseudo-critical edge is `[0, 2, 3]`.\n\n**Example 2:**\n\nConsider a similar graph with different edge weights:\n\n```\n   3\n0 ----- 1\n|       |\n|1      |4\n|       |\n|       |\n2----- 3\n   2\n```\n\nEdges: `[[0, 1, 3], [0, 2, 1], [1, 3, 4], [2, 3, 2]]`\n\n1. **Constructing the MST and Initial Weights:**\n   - MST: `[[0, 2, 1], [2, 3, 2], [0, 1, 3]]`\n   - `MST Weight`: 1 + 2 + 3 = 6\n\n2. **Finding Critical Edges:**\n   - For each edge, we calculate the MST weight after excluding it:\n     - For edge `[0, 1, 3]`: MST weight after excluding = 3 + 2 = 5 (decreased, not critical)\n     - For edge `[0, 2, 1]`: MST weight after excluding = 3 + 4 = 7 (increased, so critical)\n     - For edge `[1, 3, 4]`: MST weight after excluding = 1 + 2 = 3 (decreased, not critical)\n     - For edge `[2, 3, 2]`: MST weight after excluding = 1 + 4 = 5 (decreased, not critical)\n   - So, the critical edge is `[0, 2, 1]`.\n\n3. **Finding Pseudo-Critical Edges:**\n   - For each edge, we calculate the MST weight after including it:\n     - For edge `[0, 1, 3]`: MST weight after including = 3 + 2 + 4 = 9 (increased, not pseudo-critical)\n     - For edge `[0, 2, 1]`: MST weight after including = 1 + 2 + 2 + 3 = 8 (decreased, not pseudo-critical)\n     - For edge `[1, 3, 4]`: MST weight after including = 1 + 2 + 2 + 3 = 8 (decreased, not pseudo-critical)\n     - For edge `[2, 3, 2]`: MST weight after including = 1 + 2 + 4 = 7 (decreased, so pseudo-critical)\n   - So, the pseudo-critical edge is `[2, 3, 2]`.\n\nThese examples illustrate how the solution identifies critical and pseudo-critical edges in a given graph using Kruskal\'s algorithm and the provided code.\n\n## Complexity\n- Time complexity:\n  - Constructing the `DisjointSet`: $$O(n)$$\n  - Sorting the edges: $$O(E \\log E)$$, where $$E$$ is the number of edges.\n  - Kruskal\'s algorithm: $$O(E \\alpha(V))$$, where $$\\alpha$$ is the inverse Ackermann function and $$V$$ is the number of vertices.\n  - Overall time complexity: $$O(E \\log E + E \\alpha(V))$$\n- Space complexity:\n  - `DisjointSet`: $$O(n)$$\n  - `Graph`: $$O(E)$$\n  - `Solution`: $$O(E)$$\n  - Overall space complexity: $$O(E)$$\n\nPlease note that the time complexity of Kruskal\'s algorithm is usually dominated by $$O(E \\log E)$$ due to the sorting step, but the amortized time complexity of union-find operations using disjoint set can be considered as nearly constant ($$\\alpha(V)$$ is a very slow-growing function).\n# Code\n```\nclass DisjointSet {\n    int[] parent;\n    int[] rank;\n\n    public DisjointSet(int n) {\n        parent = new int[n];\n        rank = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i; // Initialize each vertex as its own parent\n            rank[i] = 0; // Initialize rank to 0\n        }\n    }\n\n    public int find(int x) {\n        if (parent[x] != x) {\n            parent[x] = find(parent[x]); // Path compression\n        }\n        return parent[x];\n    }\n\n    public void union(int x, int y) {\n        int rootX = find(x);\n        int rootY = find(y);\n\n        if (rootX != rootY) {\n            if (rank[rootX] < rank[rootY]) {\n                parent[rootX] = rootY; // Attach smaller rank tree under root of high rank tree\n            } else if (rank[rootX] > rank[rootY]) {\n                parent[rootY] = rootX; // Attach smaller rank tree under root of high rank tree\n            } else {\n                parent[rootY] = rootX; // Attach one tree under root of another, increment rank\n                rank[rootX]++;\n            }\n        }\n    }\n}\n\nclass Graph {\n    int se[][];\n    int n;\n\n    public Graph(int edges[][], int n) {\n        int size = edges.length;\n        se = new int[size][3];\n\n        for (int i = 0; i < edges.length; i++) {\n            se[i] = edges[i].clone();\n        }\n        Arrays.sort(se, (x, y) -> (x[2] - y[2])); // Sort edges based on weights\n        this.n = n;\n    }\n\n    public int kruskal() {\n        int sum = 0;\n\n        DisjointSet ds = new DisjointSet(n);\n\n        for (int[] e : se) {\n            int f = e[0];\n            int t = e[1];\n            int w = e[2];\n\n            int pf = ds.find(f);\n            int pt = ds.find(t);\n\n            if (pf != pt) {\n                ds.union(pf, pt); // Union the vertices if they are not in the same set\n                sum += w; // Add the weight of the edge to the total MST weight\n            }\n        }\n\n        return sum; // Return the total weight of the MST\n    }\n\n    // Other methods for calculating MST weights with specific edge inclusion/exclusion\n    // (kruskalInc and kruskalExc) can be implemented similarly.\n}\n\nclass Solution {\n\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        List<List<Integer>> res = new ArrayList<>();\n\n        res.add(new ArrayList<>()); // List to store critical edges\n        res.add(new ArrayList<>()); // List to store pseudo-critical edges\n\n        Graph g = new Graph(edges, n);\n\n        int org = g.kruskal(); // Calculate the weight of the original MST\n\n        for (int i = 0; i < edges.length; i++) {\n            int e[] = edges[i];\n\n            int exc = g.kruskalExc(e[0], e[1], e[2]); // MST weight after excluding the edge\n\n            if (org != exc) {\n                res.get(0).add(i); // If MST weight increased, edge is critical\n            } else {\n                int inc = g.kruskalInc(e[0], e[1], e[2]); // MST weight after including the edge\n\n                if (org == inc) {\n                    res.get(1).add(i); // If MST weight remains same, edge is pseudo-critical\n                }\n            }\n        }\n\n        return res;\n    }\n\n}\n\n```
['Minimum Spanning Tree', 'Java']