[Java] Kruskal + Union Find, Easy to Understand
First of all, we find the cost of a MST, and call it min_cost. Then think about the following questions: \n How to check if an edge is critical? \n How to check
First of all, we find the cost of a MST, and call it `min_cost`. Then think about the following questions: \n* How to check if an edge is critical? \n* How to check if an edge is pseudo-critical? \n\nAnswer:\n* We know that deleting a critical edge will increase the cost of MST. \n\t\tHence, if the cost after deletion is larger than the `min_cost`, then such an edge is critical.\n* We know that a pseudo-critical edge \n\t1. Exists in some MSTs. => We must use this edge to find the MST. The cost will be equal to the `min_cost`.\n\t2. Does not exists in all MSTs. => The cost after deletion is equal to the `min_cost`.\n```\nclass Solution {\n    int[][] edges;\n    int cost; // min_cost\n    DSU dsu;\n    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {\n        this.dsu = new DSU(n);\n        int[][] es = new int[edges.length][4];\n        for (int i = 0; i < edges.length; i++) {\n            es[i] = new int[]{edges[i][0], edges[i][1], edges[i][2], i};\n        }\n        Arrays.sort(es, (a, b) -> (a[2] - b[2]));\n        this.edges = es;\n        this.cost = findCost(es.length, true); // Find the min_cost.\n        Set<Integer> s1 = criticalEdges(), s2 = pseudoCriticalEdges(s1);\n        return new ArrayList<>(Arrays.asList(new ArrayList<>(s1), new ArrayList<>(s2)));\n    }\n\t\n\t// Find the cost with current edges.\n\t// skip == true means we delete this edge and then find the cost.\n\t// skip == false means we must use this edge to find the cost.\n    private int findCost(int index, boolean skip) {\n        this.dsu.reset();\n        int cost = 0;\n        if (!skip) {\n            cost += this.edges[index][2];\n            this.dsu.union(this.edges[index][0], this.edges[index][1]);\n        }\n        for (int i = 0; i < this.edges.length; i++) {\n            if (i == index) continue;\n            int[] e = this.edges[i];\n            if (!this.dsu.formCycle(e[0], e[1])) {\n                cost += e[2];\n                this.dsu.union(e[0], e[1]);\n            }\n        }\n        return cost;\n    }\n    \n\t// Find the critical edges: check if the cost after deletion is larger than the min_cost.\n    private Set<Integer> criticalEdges() {\n        Set<Integer> res = new HashSet<>();\n        for (int i = 0; i < this.edges.length; i++) {\n            if (this.cost != findCost(i, true)) {\n                res.add(edges[i][3]);\n            }\n        }\n        return res;\n    }\n    \n\t// Find the pseudo critical edges:\n\t// 1. Use this edge to find the MST. The cost will be equal to the min_cost.\n\t// 2. The cost after deletion is equal to the min_cost.\n    private Set<Integer> pseudoCriticalEdges(Set<Integer> s1) {\n        Set<Integer> res = new HashSet<>();\n        for (int i = 0; i < this.edges.length; i++) {\n\t\t\t// Note that s1 is the set of crititcal edges. \n\t\t\t// For edges in s1, the cost after deletion is larger than the min_cost.\n\t\t\t// Then the edges not in s1 are the edges that the cost after deletion is equal to the min_cost.\n            if (!s1.contains(edges[i][3]) && this.cost == findCost(i, false)) {\n                res.add(edges[i][3]);\n            }\n        }\n        return res;\n    }\n}\n\nclass DSU {\n    int[] parent, size;\n    public DSU(int n) {\n        parent = new int[n];\n        size = new int[n];\n        Arrays.fill(size, 1);\n        for (int i = 0; i < n; i++) parent[i] = i;\n    }\n    public int find(int x) {\n        if (x != parent[x]) {\n            parent[x] = find(parent[x]);\n        }\n        return parent[x];\n    }\n    public boolean formCycle(int x, int y) {\n        return find(x) == find(y);\n    }\n    public void union(int x, int y) {\n        int rootX = find(x), rootY = find(y);\n        if (rootX == rootY) return;\n        if (size[rootX] < size[rootY]) {\n            size[rootY] += size[rootX];\n            parent[rootX] = rootY;\n        } else {\n            size[rootX] += size[rootY];\n            parent[rootY] = rootX;\n        }\n    }\n    public void reset() {\n        Arrays.fill(size, 1);\n        for (int i = 0; i < parent.length; i++) parent[i] = i;\n    }\n}\n```
[]