1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

T: O(ElogE + n*Akeman + E*n*Akeman)
S: O(E + n)

```java
class Solution {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] oEdges) {
        Set<Integer> critical = new HashSet<>();
        List<Integer> pseudoCritical = new ArrayList<>();
        LinkedList<int[]> edges = new LinkedList<>();
        for (int i = 0; i < oEdges.length; i++) {
            edges.add(new int[] {oEdges[i][0], oEdges[i][1], oEdges[i][2], i});
        }

        // get original minMst
        Collections.sort(edges, (a, b) -> a[2] - b[2]); // sort -> O(ElogE)
        int minMst = getMst(edges, -1, n); // O(n*Akeman)

        // critical means, if you remove this edge, mst will be larger, so test it
        for (int i = 0; i < edges.size(); i++) { // O(E*n*Akeman)
            int newMst = getMst(edges, i, n);
            if (newMst > minMst) {
                int oldIndex = edges.get(i)[3];
                critical.add(oldIndex);
            }
        }

        // pseudoCritical means, if you add this edge first, mst is still the same as original mst
        for (int i = 0; i < edges.size(); i++) {
            int oldIndex = edges.get(i)[3];
            if (!critical.contains(oldIndex)) { // critical & pseudoCritical 是互斥的, 所以存在 critical 的必然不是 pseudoCritical
                edges.addFirst(edges.get(i)); // 先加入這個邊看看

                int newMst = getMst(edges, -1, n); 
                if (newMst == minMst) { // 看值是否會改變
                    pseudoCritical.add(oldIndex); // 不變就是 pseudoCritical
                }
                edges.removeFirst(); // 用完移掉
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>(critical));
        result.add(pseudoCritical);
        return result;
    }
    public int getMst(LinkedList<int[]> edges, int ignoreEdge, int n) {
        UnionFind uf = new UnionFind(n);

        int mstWeight = 0;
        for (int i = 0; i < edges.size(); i++) {
            int[] edge = edges.get(i);
            if (ignoreEdge == i) { // 不加邊
                continue;
            }
            if (uf.union(edge[0], edge[1])) {
                mstWeight += edge[2];
            }
        }
        return uf.getCount() == 1 ? mstWeight : Integer.MAX_VALUE;
    }
    class UnionFind {
        private int[] parent;
        int count;
        UnionFind(int n) {
            this.count = n;
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) {
                this.parent[x] = y;
                this.count--;
                return true;
            }
            return false;
        }
        private int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        private int getCount() {
            return this.count;
        }
    }
}
```