解法一：BFS

1、思路

• 通过BFS算法计算相邻城市组成的省份个数；

• 时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$。

2、代码

class Solution {
public:
    void bfs(vector<vector<int>>& isConnected, vector<bool>& isVisited, int city)
    {
        queue<int> q;
        q.push(city);

        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            isVisited[i] = true;    //标记已访问

            for (int j = 0; j < isConnected.size(); ++ j)
            {
                //将未访问过并邻接的城市放入队列中
                if (isConnected[i][j] == 1 && !isVisited[j])
                {
                    q.push(j);
                }
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<bool> isVisited(isConnected.size());
        int res = 0;

        //遍历所有城市，对每个未访问过的城市进行宽度优先搜索
        for (int city = 0; city < isConnected.size(); ++ city)
        {
            if (!isVisited[city])
            {
                bfs(isConnected, isVisited, city);
                ++ res;
            }
        }

        return res;
    }
};

解法二：DFS

1、思路

同上。

2、代码

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, vector<bool>& isVisited, int city)
    {
        isVisited[city] = true;

        for (int i = 0; i < isConnected.size(); ++ i)
        {
            if (isConnected[city][i] == 1 && !isVisited[i])
            {
                dfs(isConnected, isVisited, i);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<bool> isVisited(isConnected.size());
        int res = 0;

        for (int city = 0; city < isConnected.size(); ++ city)
        {
            if (!isVisited[city])
            {
                dfs(isConnected, isVisited, city);
                ++ res;
            }
        }

        return res;
    }
};

解法三：并查集

1、思路

• findFather函数用来寻找城市的根节点（也可以说是城市的所属省份），一旦得知城市i的根节点就记录到fathers[i]中，相当于压缩了路径；

• 若城市i与城市j相邻，则在调用isUnion函数后，判断它们是否已经合并，若没有则合并。每完成一次合并，结果res就减1；

• 时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(N)$。

2、代码

class Solution {
public:
    int findFather(vector<int>& fathers, int i) //找一座城市的根节点
    {
        if (fathers[i] != i)
        {
            //初始化：每个城市的根节点都是它自己
            fathers[i] = findFather(fathers, fathers[i]);
        }

        return fathers[i];
    }

    bool isUnion(vector<int>& fathers, int i, int j)
    {
        int fatherOfI = findFather(fathers, i);
        int fatherOfJ = findFather(fathers, j);

        if (fatherOfI != fatherOfJ)             //它们不在一个子集中
        {
            //fathers[fatherOfI] = fatherOfJ;   //反过来写也是可以的
            fathers[fatherOfI] = fatherOfJ;     //合并这俩子集
            return true;
        }

        return false;                           //已经在一个子集中，不必合并
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> fathers(isConnected.size());
        for (int i = 0; i < isConnected.size(); ++ i)
        {
            fathers[i] = i;
        }

        int res = isConnected.size();
        for (int i = 0; i < isConnected.size(); ++ i)
        {
            for (int j = i + 1; j < isConnected.size(); ++ j)
            {
                //判断两座城市是否相邻，并且是否已经在同一个子集中
                if (isConnected[i][j] == 1 && isUnion(fathers, i, j))
                {
                    res -- ;
                }
            }
        }

        return res;
    }
};