leetcode-547：省份数量

题目

题目连接

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

解题

方法一：并查集

class UnionFind{
    
private:
    vector<int> parent;
    int setNum;
public:
    UnionFind(int n){
    
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
        setNum=n;//初始集合数量为n
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        parent[index]=find(parent[index]);
        return parent[index];
    }
    void unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
    //如果两个集合不是同一个，那么合并集合，集合数量减一
            parent[p1]=p2;
            setNum--;
        }
    }
    int getSetNum(){
    
        return setNum;
    }
};

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int n=isConnected.size();
        UnionFind uf(n);
        for(int i=0;i<n;i++){
    
            for(int j=0;j<n;j++){
    
                if(isConnected[i][j]==1){
    
                    uf.unite(i,j);
                }
            }
        }
        return uf.getSetNum();
    }
};

方法二：dfs

class Solution {
    
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int n=isConnected.size();
        int res=0;
        vector<bool> visit(n);
        for(int i=0;i<n;i++){
    
            if(!visit[i]){
    
                dfs(isConnected,visit,i);
                res++;
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& isConnected,vector<bool>& visit,int i){
    
        visit[i]=true;
        for(int j=0;j<visit.size();j++){
    
            if(!visit[j]&&isConnected[i][j]){
    
                dfs(isConnected,visit,j);
            }
        }
    }
};