leetcode 547.省份数量 并查集_有 n 个城市,其中一些彼此相连,另……没有相连。如果城市 a 与城市 b 直接相

题目描述

省份数量

思路

直接利用并查集的思想即可。
并查集

代码

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> p(210);
        for(int i=0;i<isConnected.size();i++)
            p[i]=i;  //初始化并查集的数组，每个元素的根节点都为自身，也即没有父结点、根节点，都是独立的

        for(int i=0;i<isConnected.size();i++)
            for(int j=0;j<isConnected[0].size();j++)
            {
                if(isConnected[i][j]==1)
                {
                    int a=find(i,p);
                    int b=find(j,p);
                    if(a!=b)  //如果不是一个集合
                        p[b]=a; //路径压缩合并
                }
            }
     //怎么计算一共有多少个集合？
        int res=0;
        for(int i=0;i<isConnected.size();i++)
            if(p[i]==i) res++;  //只要数一共有多少节点被作为根节点即可，根节点与集合个数一一对应
        return res;        
    }
    //路径压缩去查找的同时压缩路径
    int find(int x,vector<int>& p)
    {
        if(x!=p[x]) p[x]=find(p[x],p);
        return p[x];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31