Leetcode1489-找到最小生成树里的关键边和伪关键边

kruskal+并查集

题目数据量不大，因此考虑暴力枚举最小生成树的做法。

用到的数据结构：

数组vis：标记该边是否为关键边

数组real，fake：分别记录关键边和伪关键边

并查集p

①为所有边添加上一个编号，然后按边权升序排列。

②先对整个图跑kruskal求一遍最小生成树的权值w。

③枚举所有边，除去该边求整个图的最小生成树的权值nw，若和w不同，则说明该边为关键边，加入到real数组中，并在vis数组中标记它。

④枚举所有非关键边，先把该边的两端结点加入到并查集中，即把该边强行加入到最小生成树中，再求整颗最小生成树的权值nw，如果和w相同，则表示即使整个图没有这条非关键边，最小生成树的权值仍为w，也即该边为伪关键边，加入到fake数组中。

⑤把real和fake作为答案返回。

class Solution {
public:
    vector<int> p=vector<int>(110);
    int findd(int x){
        return p[x]==x?x:p[x]=findd(p[x]);
    }
    void unionn(int x,int y){
        x=findd(x),y=findd(y);
        p[x]=y;
    }
    vectorint>> findCriticalAndPseudoCriticalEdges(int n, vectorint>>& edges){
        int m=edges.size();
        vector<int> vis(m,0);
        vector<int> real,fake;
        vectorint>> ans;
        for(int i=0;ipush_back(i);
        sort(edges.begin(),edges.end(),[](const auto &a,const auto &b){
            return a[2]2];
        });
        int w=0;
        iota(p.begin(),p.end(),0);
        for(int i=0;i
            int x=findd(edges[i][0]);
            int y=findd(edges[i][1]);
            if(x!=y){
                unionn(x,y);
                w+=edges[i][2];
            }
        }
        for(int i=0;i
            int nw=0;
            iota(p.begin(),p.end(),0);
            for(int j=0;j
                if(i==j) continue;
                int x=findd(edges[j][0]);
                int y=findd(edges[j][1]);
                if(x!=y){
                    unionn(x,y);
                    nw+=edges[j][2];
                }
            }
            if(nw!=w){
                real.push_back(edges[i][3]);
                vis[edges[i][3]]=1;
            }
        }
        for(int i=0;i
            if(vis[edges[i][3]]) continue;
            iota(p.begin(),p.end(),0);
            int nw=edges[i][2];
            unionn(edges[i][0],edges[i][1]);
            for(int j=0;j
                if(i==j) continue;
                int x=findd(edges[j][0]);
                int y=findd(edges[j][1]);
                if(x!=y){
                    unionn(x,y);
                    nw+=edges[j][2];
                }
            }
            if(nw==w) fake.push_back(edges[i][3]);
        }
        ans.push_back(real),ans.push_back(fake);
        return ans;
    }
};

时间复杂度：O（m^2·α(n)），α(n)为并查集的复杂度。

空间复杂度：O（m+n）