LeetCode每日一题：连通网络的操作次数

传送门

思路

力扣这个月的daily哟，已经变成了并查集的形状了。

题意很裸，本质上就是求联通分量的个数，和LeetCode每日一题：移除最多的同行或同列石头很像。两个连通分量相接通需要1条边，n个就需要n-1条边，求这个n并返回n-1作为答案就行了。

根据题设，显然有connections.size() < n-1时，返回-1.

代码

class Solution {
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;
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        const int m = connections.size();
        if(m < n - 1) return -1;
        init(n);
        int ans = 0;

        for (int i = 0; i < m; i++) {
            merge(connections[i][0], connections[i][1]);
        }

        return cnt - 1;
    }
};