原题链接：Leetcode 547. 省份数量

DFS

class Solution {
public:
    vector<int> visited;
    void dfs(vector<vector<int>>& isConnected,int x,int n)
    {
        for(int i=0;i<n;i++)
        {
            if(!visited[i] && isConnected[i][x])
            {
                visited[i]=1;
                dfs(isConnected,i,n);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        visited.resize(n);
        int num=0;
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                dfs(isConnected,i,n);
                num++;
            }
        }
        return num;
    }
};

BFS

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        vector<int> visited;
        visited.resize(n);
        int num=0;
        queue<int> q;
        for(int i=0;i<n;i++)
        {
            if(!visited[i])
            {
                q.push(i);
                while(!q.empty())
                {
                    int x=q.front();
                    q.pop();
                    for(int j=0;j<n;j++)
                    {
                        if(!visited[j] && isConnected[x][j])
                        {
                            visited[j]=1;
                            q.push(j);
                        }
                    }
                }
                num++;
            }
        }
        return num;
    }
};

并查集

class Solution { 
public:
    map<int,int> fa;
    int findfather(int i)
    {
        if(fa[i]==i) return i;
        else return findfather(fa[i]);
    }
    void Union(int x,int y)
    {
        int fx=findfather(x);
        int fy=findfather(y);
        if(fx!=fy) fa[fx]=fy;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        for(int i=0;i<n;i++) fa[i]=i;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isConnected[i][j])  Union(i,j);
            }
        }
        set<int> s;
        for(int i=0;i<n;i++)
        {
            int x=findfather(i);
            s.insert(x);
        }
        return s.size();
    }
};