LeetCode每日一题：保证图可完全遍历

传送门

思路

这是一道hard题，但感觉并不是很hard。

题目要求一个无向图在保证其连通性下能删除的最大边数。那么用并查集的思想，可以理解为“给一个n个节点的图添加数量最少的无向边使其连通。”

为Alice和Bob两人各单独维护一个并查集，挨个加入每条边。如果当前边的两个顶点已经连通了，那么这个边就是一个多余边，直接计数器++。

值得注意的是，添加边的时候应该优先考虑type3的边，即公共边。因为公共边是共用的，考虑一种极端情况：对于同一个图，图中仅有type1、2边与仅有type3边。

因为对于每一个人，都要确保图的连通性，所以前者情况下，边数需要2*n=2n条，因为私有边不能公用；而后者情况下仅需要n条边，因为type3的边可以共用。以这个极端例子可以讨论在添加边的时候公有边优先级更高。

考虑非法状态，如果题目所给图对于二人中至少一人是非连通的，那么显然应该返回-1。

代码

class Disjoint {
private:
    unordered_map<int, int> father;
    unordered_map<int, int> rank;
public:
    int cnt;
    void init(int n) {
        cnt = n;
        for (int i = 0; i < n; i++) {
            rank[i] = 1;
            father[i] = i;
        }
    }

    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    bool merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);

        if (fx == fy) {
            return false;
        }

        if(rank[fx] < rank[fy]) {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        father[fy] = fx;
        cnt--;
        return true;
    }
};

class Solution {
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        int ans = 0;
        Disjoint Alice, Bob;
        Alice.init(n);
        Bob.init(n);

        for (auto el : edges) {
            if (el[0] == 3) {
                if (Alice.find(el[1]) == Alice.find(el[2]) && 
                    Bob.find(el[1]) == Bob.find(el[2])) {
                    ans++;
                } else {
                    Alice.merge(el[1], el[2]);
                    Bob.merge(el[1], el[2]);
                }
            }
        }

        for (auto el : edges) {
            if (el[0] == 1) {
                if (Alice.find(el[1]) == Alice.find(el[2])) {
                    ans++;
                } else {
                    Alice.merge(el[1], el[2]);
                }
            } else if (el[0] == 2) {
                if (Bob.find(el[1]) == Bob.find(el[2])) {
                    ans++;
                } else {
                    Bob.merge(el[1], el[2]);
                }
            }
        }

        if (Alice.cnt != 1 || Bob.cnt != 1) return -1;

        return ans;
    }
};