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

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

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

&nbsp;
Example 1:



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:



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.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 100
	1 &lt;= edges.length &lt;= min(200, n * (n - 1) / 2)
	edges[i].length == 3
	0 &lt;= ai &lt; bi &lt; n
	1 &lt;= weighti&nbsp;&lt;= 1000
	All pairs (ai, bi) are distinct.


class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        def find(v, parent):
            if parent[v] != v:
                parent[v] = find(parent[v], parent)
            return parent[v]
        def union(u,v, parent):
            parent[find(u,parent)] = find(v,parent)
        edges = [(u,v,w,i) for i, (u,v,w) in enumerate(edges)]
        edges.sort(key = lambda e:e[2])
        def find_mst_without_this_edge(idx):
            parent = list(range(n))
            res = 0
            for i, (u, v, w, _) in enumerate(edges):
                if i == idx: continue
                if find(u, parent) != find(v, parent):
                    res += w
                    union(u, v, parent)
            root = find(0, parent)
            return res if all(find(i, parent) == root for i in range(n)) else float('inf')
        def find_mst_with_this_edge(idx):
            parent = list(range(n))
            u0, v0, w0, _ = edges[idx]
            res = w0
            union(u0,v0,parent)
            for i, (u, v, w, _) in enumerate(edges):
                if i == idx:
                    continue
                if find(u, parent) != find(v, parent):
                    res += w
                    union(u, v, parent)
            root = find(0, parent)
            return res if all(find(i, parent) == root for i in range(n)) else float('inf')
        base_mst_wgt = find_mst_without_this_edge(-1)
        cri, pcri = set(), set()
        for i in range(len(edges)):
            wgt_excl = find_mst_without_this_edge(i)
            if wgt_excl > base_mst_wgt:
                cri.add(edges[i][3])
            else:
                wgt_incl = find_mst_with_this_edge(i)
                if wgt_incl == base_mst_wgt:
                    pcri.add(edges[i][3])
        return [cri, pcri]
class Solution {
    static class UnionFind{
        int[]parent;
        int[]rank;
        int comp = 0;
        UnionFind(int n){
            parent = new int[n];
            rank = new int[n];
            comp = n;
            for(int i=0;i<n;i++){
                parent[i] = i;
                rank[i] = 0;
            }
        }
        
        int find(int x){
            if(parent[x] == x){
                return x;
            }else{
                parent[x] = find(parent[x]);
                return parent[x];
            }
        }
        
        boolean union(int X,int Y){
            int x = find(X);
            int y = find(Y);
            if(x == y){
                return false;
            }
            
            if(rank[x] < rank[y]){
                parent[x] = y;
            }else if(rank[y] < rank[x]){
                parent[y] = x;
            }else{
                parent[y] = x;
                rank[x]++;
            }
            comp--;
            return true;
        }
        
        boolean isConnected(){
            return comp == 1;
        }
        
    }
    
    static class Edge implements Comparable<Edge>{
        int u;
        int v;
        int wt;
        Edge(int u,int v,int wt){
            this.u = u;
            this.v = v;
            this.wt = wt;
        }
        public int compareTo(Edge o){
            return this.wt - o.wt;
        } 
    }
    public int buildMST(int n,int[][]edges,int[]edgeSkip,int[]edgePick){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        
        for(int[]edge : edges){
            if(edge == edgeSkip){
                continue;
            }else if(edge == edgePick){
                continue;
            }
            int u = edge[0];
            int v = edge[1];
            int wt = edge[2];
            pq.add(new Edge(u,v,wt));
        }
        
        UnionFind uf = new UnionFind(n);
        int cost = 0;
        
        if(edgePick != null){
            uf.union(edgePick[0],edgePick[1]);
            cost += edgePick[2];
        }
        while(pq.size() > 0){
            Edge rem = pq.remove();
            if(uf.union(rem.u,rem.v) == true){
                cost += rem.wt;
            }
        }
        
        if(uf.isConnected() == true){
            return cost;
        }else{
            return Integer.MAX_VALUE;
        }
    }
    
    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
        int mstCost = buildMST(n,edges,null,null);
        
        ArrayList<Integer> critical = new ArrayList<>();
        ArrayList<Integer> pcritical = new ArrayList<>();
        
        for(int i=0;i<edges.length;i++){
            int []edge = edges[i];
            
            int mstCostWithoutEdge = buildMST(n,edges,edge,null);
            if(mstCostWithoutEdge > mstCost){
                critical.add(i);        //Critical edge index
            }else{
                int mstCostWithEdge = buildMST(n,edges,null,edge);
                if(mstCostWithEdge > mstCost){
                    //redundant
                }else{
                    pcritical.add(i);   //pseduo critical edge index
                }
            }
        }
        
        List<List<Integer>> res = new ArrayList<>();
        res.add(critical);
        res.add(pcritical);
        return res;
    }
}
class UnionFind{
private:
    vector<int> parent_;
    vector<int> rank_;
    int sets_;
public:
    UnionFind(int n)
    {
        init(n);
    }
    void init(int n)
    {
        sets_ = n;
        parent_.resize(n);
        rank_.resize(n);
        iota(parent_.begin(),parent_.end(),0);
        fill(rank_.begin(),rank_.end(),1);
    }
    int find(int u)
    {
        return parent_[u] == u ? u: parent_[u] = find(parent_[u]);
    }
    bool join(int u,int v)
    {
        u = find(u);
        v = find(v);

        if(u==v)
        {
            return false;
        }
        
        if(rank_[u]<rank_[v])
        {
            swap(u,v);
        }

        rank_[u] += rank_[v];
        parent_[v] = u;

        sets_ --;
        return true;
    }
    bool united()
    {
        return sets_ == 1;
    }
};
class Solution {
public:
    vector<int> edges_idx_;
    int kruskal(const int n, const int removed_edge_idx,const int init_edge_idx,
    const vector<vector<int>> &edges)
    {
        UnionFind graph(n);
        int edges_size = edges.size();
        int total = 0;

        if(init_edge_idx != -1)
        {
            graph.join(edges[init_edge_idx][0],edges[init_edge_idx][1]);
            total += edges[init_edge_idx][2];
        }

        
        for(int i = 0; i<edges_size; ++i)    
        {
            int edge_idx = edges_idx_[i];

            if(edge_idx == removed_edge_idx)
            {
                continue;
            }

            int u = edges[edge_idx][0];
            int v = edges[edge_idx][1];

            if(graph.join(u,v))
            {
                total+= edges[edge_idx][2];
            }
        }
        
        return graph.united() ? total : INT_MAX;

    }
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
       int edges_size = edges.size();

       edges_idx_.resize(edges_size);

       iota(edges_idx_.begin(),edges_idx_.end(),0);
       
       sort(edges_idx_.begin(),edges_idx_.end(),[&edges](int a, int b){
           return edges[a][2] < edges[b][2];
       });

       int mst = kruskal(n,-1,-1,edges);
       

       vector<int> critical;
       vector<int> psudo;
       
       for(int i = 0; i< edges_size; ++i)
       {
           int edge_idx = edges_idx_[i];
           int total = kruskal(n,-1,edge_idx,edges);
           
           if(total == mst)
           {
               total = kruskal(n,edge_idx,-1,edges);
               if(total > mst)
               {
                   critical.push_back(edge_idx);
               }
               else{
                   psudo.push_back(edge_idx);
               }
           }
       }

       return {critical,psudo};
       
    }
};
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var findCriticalAndPseudoCriticalEdges = function(n, edges) {
	// find and union utils
    const find = (x, parent) => {
        if (parent[x] === -1) { return x }
        const y = find(parent[x], parent)
        parent[x] = y
        return y
    }
    const union = (a, b, parent) => {
        a = find(a, parent)
        b = find(b, parent)
        if (a === b) { return false }
        parent[a] = b
        return true
    }

	// sort and group edges by cost
    const map = {}
    edges.forEach(([a, b, cost], i) => {
        map[cost] = map[cost] || []
        map[cost].push([a, b, i])
    })
    const costs = Object.keys(map).sort((a, b) => a - b)

	// check by group
    const check = (edges, parent) => {
        let nextParent
        let count

		// travel with a skipped point
		// if skip === -1, skip nothing and update count and nextParent.
        const travel = skip => {
            const p = [...parent]
            const result = []
            edges.forEach(([a, b, i]) => {
                if (i === skip) { return }
                if (union(a, b, p)) { result.push(i) }
            })
            if (skip === -1) {
                count = result.length
                nextParent = p
            }
            return result
        }

		// get default count and nextParent.
        travel(-1)

		// special case: there is only one edge in this group
        if (edges.length === 1) {
            if (count === 0) { return [[], [], 0, parent] }
            return [[edges[0][2]], [], 1, nextParent]
        }

		// aList -> critical, bList -> pseudo
        const aList = {}
        const bList = {}
        edges.forEach(([a, b, i]) => {
            if (find(a, parent) === find(b, parent)) { return }
            const result = travel(i)
            result.length < count ? aList[i] = true : bList[i] = true
        })
        return [Object.keys(aList), Object.keys(bList), count, nextParent]
    }

	// init traversal state
    const critical = []
    const pseudo = []
    let count = 0
    let parent = new Array(n).fill(-1)

	// travel by cost group until all points visited
    for (let i = 0; i < costs.length; i++) {
        const [aList, bList, newCount, nextParent] = check(map[costs[i]], parent)
        critical.push(...aList)
        pseudo.push(...bList)
        count += newCount
        parent = nextParent
        if (count === n - 1) { break }
    }

	return [critical, pseudo]
};
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree