力扣--并查集547.省份数量-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣--并查集547.省份数量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣--并查集547.省份数量,leetcode,算法,数据结构,c++,c语言

思路分析：文章来源地址https://www.toymoban.com/news/detail-843468.html

首先定义变量 fa 用于记录并查集，以及城市数量 n。
定义了并查集的两个函数，find 用于查找节点的根节点，togother 用于合并两个节点所在的集合。
在公共函数 findCircleNum 中，初始化并查集，然后遍历 isConnected 数组，将相连的城市进行合并。
最后使用 visited 数组记录每个城市是否已经被访问过，然后统计省份的数量并返回。


class Solution {
  
    int fa[201]; // 并查集数组，用于记录节点的父节点
    int n; // 城市数量
    
    // 定义并查集的查找函数，用于查找节点 x 的根节点（即所属集合的代表节点）
    int find(int x) {
        // 如果节点 x 的父节点就是它自己，则返回 x
        if (fa[x] == x)
            return x;
        // 否则，递归地查找 x 的父节点，并返回结果
        else
            return find(fa[x]);
    }
    
    // 定义并查集的合并函数，用于合并节点 x 和节点 y 所在的两个集合
    void togother(int x, int y) {
        // 将节点 x 所在集合的根节点设为节点 y 所在集合的根节点
        fa[find(x)] = find(y);
    }
    
public:
    // 定义一个公共函数，用于计算省份的数量
    int findCircleNum(vector<vector<int>>& isConnected) {
        // 获取城市数量
        n = isConnected.size();
        
        // 初始化并查集，将每个节点的父节点设为它自己
        for (int i = 0; i < n; i++)
            fa[i] = i;
        
        // 遍历 isConnected 数组，将相连的城市进行合并
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1)
                    togother(i, j);
            }
        }
        
        // 使用 visited 数组记录每个城市是否已经被访问过
        vector<bool> visited(n, false);
        int count = 0; // 记录省份的数量
        
        // 遍历每个城市，对于每个城市，如果其所在集合的根节点尚未被访问过，则将其标记为已访问，并增加省份数量
        for (int i = 0; i < n; i++) {
            if (visited[find(i)] == false) {
                count++;
                visited[find(i)] = true;
            }
        }
        
        // 返回省份的数量
        return count;
    }
};

到了这里，关于力扣--并查集547.省份数量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！