> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree.md).

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

Given a weighted undirected connected graph with `n` vertices numbered from `0` to `n-1`, and an array `edges` where `edges[i] = [fromi, toi, weighti]` represents a bidirectional and weighted edge between nodes `fromi` and `toi`. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find *all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph*. An MST edge whose deletion from the graph would cause the MST weight to increase is called a *critical edge*. A *pseudo-critical edge*, on the other hand, is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/06/04/ex1.png)

```
Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/06/04/ex2.png)

```
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
```

**Constraints:**

* `2 <= n <= 100`
* `1 <= edges.length <= min(200, n * (n - 1) / 2)`
* `edges[i].length == 3`
* `0 <= fromi < toi < n`
* `1 <= weighti <= 1000`
* All pairs `(fromi, toi)` are distinct.

```java
class Solution {
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        List<Integer> criticals = new ArrayList<>();
        List<Integer> pseduos = new ArrayList<>();
        // Map of edges -> index
        Map<int[], Integer> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++)
            map.put(edges[i], i);
        // Sorting edges on basis of weight
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        // Minimum cost when all the edges are allowed to use
        int minCost = buildMST(n, edges, null, null);
        // Ignore edges one by one
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int index = map.get(edge);
            int costWithout = buildMST(n, edges, null, edge);
            // Critical Edge
            if (costWithout > minCost)
                criticals.add(index);
            else {
                int costWith = buildMST(n, edges, edge, null);
                // If we can acheive MST (min sum tree) with this edge included
                if (costWith == minCost)
                    pseduos.add(index);
            }
        }
        return Arrays.asList(criticals, pseduos);
    }

    public int buildMST(int n, int[][] edges, int[] pick, int[] skip) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
        int[] rank = new int[n];
        Arrays.fill(rank, 1);
        int cost = 0, edgesPicked = 0;
        // Force picking the "pick" edge
        if (pick != null) {
            union(parent, rank, pick[0], pick[1]);
            cost += pick[2];
            edgesPicked++;
        }
        // Creating MST while skipping "skip" edge
        for (int[] edge : edges)
            if (edge != skip && !union(parent, rank, edge[0], edge[1])) {
                cost += edge[2];
                edgesPicked++;
            }
        return edgesPicked == n - 1 ? cost : Integer.MAX_VALUE;
    }

    public int find(int[] parent, int node) {
        if (node != parent[node])
            parent[node] = find(parent, parent[node]);
        return parent[node];
    }

    public boolean union(int[] parent, int[] rank, int node1, int node2) {
        int p1 = find(parent, node1);
        int p2 = find(parent, node2);
        if (p1 == p2)
            return true;
        if (rank[p1] == rank[p2]) {
            parent[p1] = p2;
            rank[p2]++;
        } else if (rank[p1] > rank[p2])
            parent[p2] = p1;
        else
            parent[p1] = p2;
        return false;
    }
}
```