Leetcode|并查集|547. 省份数量

1 并查集

代码语言：javascript复制

class UnionFind {
public:
    int count;
    vector<int> parent, size;

    UnionFind(int n) {
        count = n;
        parent.resize(n);
        size.resize(n);
        for (int i = 0; i < n; i  ) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    void unite(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        if (rootA == rootB) return;
        if (size[rootA] < size[rootB]) {
            parent[rootA] = rootB;
            size[rootB]  = size[rootB];
        } else {
            parent[rootB] = parent[rootA];
            size[rootA]  = size[rootB];
        }
        count--;
    }

    bool connected(int a, int b) {
        int rootA = find_root(a);
        int rootB = find_root(b);
        return rootA == rootB;
    }

    int find_root(int node) {
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }
        return node;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int size = isConnected.size();
        if (size == 1) return 1;
        UnionFind uf(size);
        for (int i = 0; i < size; i  ) 
            for (int j = 0; j < size; j  ) 
                // 只要连通就合并
                if (isConnected[i][j] == 1) uf.unite(i, j);
        return uf.count;
    }
};

leetcode

0 人点赞