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

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

````java
```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;
        }
    }
}
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/graph-ii/mst-kruskals-algo/1489.-find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.