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

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

<p>Note that you can return the indices of the edges in any order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/ex1.png" style="width: 259px; height: 262px;" /></p>

<pre>
<strong>Input:</strong> n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
<strong>Output:</strong> [[0,1],[2,3,4,5]]
<strong>Explanation:</strong> The figure above describes the graph.
The following figure shows all the possible MSTs:
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/msts.png" style="width: 540px; height: 553px;" />
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2020/06/04/ex2.png" style="width: 247px; height: 253px;" /></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
<strong>Output:</strong> [[],[0,1,2,3]]
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= edges.length &lt;= min(200, n * (n - 1) / 2)</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= a<sub>i</sub> &lt; b<sub>i</sub> &lt; n</code></li>
	<li><code>1 &lt;= weight<sub>i</sub>&nbsp;&lt;= 1000</code></li>
	<li>All pairs <code>(a<sub>i</sub>, b<sub>i</sub>)</code> are <strong>distinct</strong>.</li>
</ul>

using vi = vector<int>;
using vvi = vector<vi>;

struct Edge{
    int a;
    int b;
    int w;
    int ind;
};

class dsu{
    public:
    vi parent;
    vi rank;

    dsu(int n){
        rank.assign(n, 1);
        for(int i=0; i<n; i++) parent.push_back(i);
    }

    int find(int a){
        if(parent[a] == a)return a;
        else return parent[a] = find(parent[a]);
    }

    void merge(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b) return;

        if(rank[b] > rank[a]) swap(a, b);

        rank[a] += rank[b];

        parent[b] = a;
    }
};

class Solution {
public:
    int m;
    int n;
    static bool cmp(Edge a, Edge b){
        return a.w < b.w;
    }

    bool check(dsu &uf){
        int p = uf.find(0);

        for(int i=1; i<n; i++)
        if(uf.find(i) != p) return false;
        return true;
    }

    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& _edges) {
        m = _edges.size();
        this->n = n;

        vi crit(m), non_crit(m);
        vector<Edge> edges;

        for(int i=0; i<m; i++){
            Edge k;
            k.a = _edges[i][0];
            k.b = _edges[i][1];
            k.w = _edges[i][2];
            k.ind = i;

            edges.push_back(k);
        }

        sort(edges.begin(), edges.end(), cmp);


        int min_wt = 0;

        dsu uf(n);

        for(int i=0; i<m; i++){
            Edge e = edges[i];

            if(uf.find(e.a) != uf.find(e.b)){
                uf.merge(e.a, e.b);
                min_wt += e.w;
            }
        }

        // cout<<min_wt<<"\n";



        for(int i=0; i<m; i++){
            dsu unf(n);
            int wt = 0;

            for(int j=0; j<m; j++){
                if(j == i) continue;

                Edge e = edges[j];

                if(unf.find(e.a) != unf.find(e.b)){
                    // cout<<"edge"<<e.a<<" "<<e.b<<"\n";
                    unf.merge(e.a, e.b);
                    wt += e.w;
                }
            }


            // for(int k=0; k<n; k++) cout<<unf.find(k)<<" ";
            // cout<<"\n";
            

            if(min_wt < wt || !check(unf)) crit[edges[i].ind] = 1;
        }

        for(int i=0; i<m; i++){
            dsu unf(n);

            unf.merge(edges[i].a, edges[i].b);
            int wt = edges[i].w;

            for(int j=0; j<m; j++){
                if(j == i) continue;

                Edge e = edges[j];

                if(unf.find(e.a) != unf.find(e.b)){
                    unf.merge(e.a, e.b);
                    wt += e.w;
                }
            }

            if(min_wt < wt) non_crit[edges[i].ind] = 1;
        }

        vvi ans(2);

        for(int i=0; i<m; i++){
            if(crit[i]) ans[0].push_back(i);
            else if(!non_crit[i]) ans[1].push_back(i);
        }

        return ans;
        
    }
};
38846