1489. 找到最小生成树里的关键边和伪关键边

1489. 找到最小生成树里的关键边和伪关键边

应该是某个周赛最后一题

kruskal的并查集

也可以用tarjan，但是暂时不会QAQ

class UnionFind{
    public:
    vector<int>p;
    vector<int>size;
    int n;
    int setcnt;

    UnionFind(int _n):n(_n),setcnt(_n){
        p.resize(n);
        for(int i=0;i<n;i++)p[i]=i;
    }

    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }
    bool merge(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return false;
        if(a>b)swap(a,b);
        p[b]=a;
        setcnt--;
        return true;
    }
};

class Solution {
public:
    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        int m=edges.size();
        for(int i=0;i<m;i++){
            edges[i].push_back(i);
        }
        sort(edges.begin(),edges.end(),[](const vector<int>&u,const vector<int>&v){
            return u[2]<v[2];
        });
        UnionFind uf(n);

        int v=0,setcnt=0;
        for(int i=0;i<m;i++){
            int a=edges[i][0],b=edges[i][1];

            if(uf.merge(a,b)){
                v+=edges[i][2];
            }
        }
        setcnt=uf.setcnt;

        vector<vector<int>>res(2);

        for(int i=0;i<m;i++){
            uf= UnionFind(n);
            int tmp=0;
            for(int j=0;j<m;j++){
                int a=edges[j][0],b=edges[j][1];
                if(i!=j && uf.merge(a,b)){
                    tmp+=edges[j][2];
                }
            }
            if(uf.setcnt>1 || uf.setcnt==1 && tmp>v){
                res[0].push_back(edges[i][3]);
                continue;  // 如果是关键边，就不是伪关键边，直接跳过
            }

            uf= UnionFind(n);
             tmp=edges[i][2];
            uf.merge(edges[i][0],edges[i][1]);

            for(int j=0;j<m;j++){
                int a=edges[j][0],b=edges[j][1];
                if(i!=j && uf.merge(a,b)){
                    tmp+=edges[j][2];
                }
            }
            if(tmp==v){
                res[1].push_back(edges[i][3]);
            }
        }
        return res;
    }
};