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

分类：图论、最小生成树、并查集

首先，用正常方法求出生成最小生成树的cost

然后遍历每一条边：

• 如果去掉这条边，图不连通或者生成树cost2>cost，那么说这条边是关键边
• 如果一开始就连接这条边，生成树cost2==cost，那么说明这条边是伪关键边
• 其他，说明边不需要
• 关键边同样满足伪关键边情况，伪关键边同样满足不需要的边的情况，所以依次判断关键边、伪关键边

class UnionFind{
private:
    unordered_map<int, int> u;
public:
    int root(int i){
        if(!u.count(i))
            u[i] = i;
        return u[i] == i? i : u[i] = root(u[i]);
    }

    void connect(int i, int j){
        u[root(i)] = root(j);
    }

    bool isConnected(int i, int j){
        return root(i) == root(j);
    }
};

class Edge{
public:
    int from, to, weight;
    Edge(int f, int t, int w):from(f), to(t), weight(w){}
};

class Compare{
public:
    bool operator() (const Edge& a, const Edge& b){
        return a.weight > b.weight;
    }
};

class Solution {
public:
    int kruskal(vector<Edge>& edges, UnionFind u, int n){
        priority_queue<Edge, vector<Edge>, Compare> q(edges.begin(), edges.end());
        
        int cost = 0, edgesCnt = 0;
        while(!q.empty()){
            Edge e = q.top(); q.pop();
            if(!u.isConnected(e.from, e.to)){
                u.connect(e.from, e.to);
                cost += e.weight;
                edgesCnt += 1;
            }
        }

        return n-1 == edgesCnt ? cost : INT_MAX;
    }

    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
        vector<Edge> edges2;
        for(vector<int> & v : edges){
            edges2.push_back(Edge(v[0], v[1], v[2]));
        }

        int cost = kruskal(edges2, UnionFind(), n);
        vector<int> critical, pseudoCritical;
        for(int i=0; i<edges2.size(); i++){
            vector<Edge> tmpEdge; UnionFind tmpU;
            for(int j=0; j<edges2.size(); j++){
                if(i==j) continue;
                tmpEdge.push_back(edges2[j]);
            }
            
            bool isCritical = (kruskal(tmpEdge, UnionFind(), n) > cost);
            if (isCritical){
                critical.push_back(i);
            }else{
                tmpU.connect(edges2[i].from, edges2[i].to);
                bool isPseudoCritical = (kruskal(tmpEdge, tmpU, n-1)+edges2[i].weight == cost);
                if(isPseudoCritical) pseudoCritical.push_back(i);
            }
        }

        return {critical, pseudoCritical};
    }
}; /* 5.9% = = **/

减少不必要的排序过程；并查集容器改为使用vector，unordered_map属实耗时过多

class UnionFind{
private:
    vector<int> u;
    vector<int> sz;
public:
    int member;
    UnionFind(int n):member(n), u(n), sz(n, 1){
        iota(u.begin(), u.end(), 0);
    }
    int root(int i){
        return u[i] == i? i : u[i] = root(u[i]);
    }

    bool connect(int i, int j){
        int ri = root(i), rj = root(j);
        if(ri == rj){
            return false;
        }
        if(sz[ri] < sz[rj]){
            swap(ri, rj);
        }
        u[rj] = ri;
        sz[ri] += sz[rj];
        member--;
        return true; 
    }
};

class Solution {
public:
    static bool compare(const vector<int>& a, const vector<int>& b){
        return a[2] < b[2];
    }
    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(), compare);
        
        int cost = 0; UnionFind u(n);
        for(int i=0; i<m; i++){
            if(u.connect(edges[i][0], edges[i][1])){
                cost += edges[i][2];
            }
        }

        vector<vector<int> > res(2, vector<int>());
        for(int i=0; i<m; i++){
            int cost1=0; UnionFind u1(n);
            for(int j=0; j<m; j++){
                if(j!=i && u1.connect(edges[j][0], edges[j][1])){
                    cost1+=edges[j][2];
                }
            }
            if(u1.member!=1 || cost1 > cost){
                res[0].push_back(edges[i][3]);
                continue;
            }

            cost1=edges[i][2]; u1 = UnionFind(n);
            u1.connect(edges[i][0], edges[i][1]);
            for(int j=0; j<m; j++){
                if(j!=i && u1.connect(edges[j][0], edges[j][1])){
                    cost1+=edges[j][2];
                }
            }
            if(u1.member == 1 && cost1 == cost){
                res[1].push_back(edges[i][3]);
            }
        }
    
        return res;
    }
};/* 32.8% **/

2021/01/21