【深度优先搜索实战】力扣547题：省份数量问题的图论解法

题目解读‌
我们面对的是一个典型的图论问题：给定一个城市的连接矩阵，需要计算其中相互连通的城市群（省份）数量。这个问题可以抽象为无向图中的连通分量计算，每个城市代表图中的一个节点，城市之间的连接关系代表图中的边。题目要求我们找出这些节点形成了多少个互不连通的子图，这在实际应用中可以用来解决社交网络中的朋友圈划分、计算机网络中的连通区域等问题。

解题思路‌
使用深度优先搜索(DFS)的策略，首先将邻接矩阵转换为邻接表的形式存储，这样可以更高效地进行图遍历。然后初始化一个标记数组来记录哪些节点已经被访问过。对于每个未被访问的节点，执行DFS遍历，将所有与之相连的节点标记为已访问。每次从一个新节点开始的DFS遍历就对应着一个新的连通分量（省份）。最后统计进行了多少次这样的DFS遍历，就是所求的省份数量。

代码注释

class Solution {
public:
    vector<int> edge[201]; // 邻接表存储图的连接关系
    int flag[201]={0}; // 标记数组，记录节点是否被访问过
    int n; // 城市总数
    
    // 深度优先搜索函数
    void delconnect(int now){
        if(flag[now])return;       // 如果已经访问过则返回
        flag[now]=true;            // 标记当前节点为已访问
        for(int i=0;i<edge[now].size();i++){
            delconnect(edge[now][i]); // 递归访问所有相邻节点
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int ret=0; // 省份计数器
        n=isConnected.size(); // 获取城市数量
    
        // 将邻接矩阵转换为邻接表
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(isConnected[i][j])
                    edge[i].push_back(j);
            }
        }
    
        // 遍历所有城市，统计连通分量
        for(int i=0;i<n;i++){
            if(!flag[i]){          // 如果该城市未被访问过
                delconnect(i);     // 执行DFS遍历
                ret++;             // 增加省份计数
            }
        }
        return ret;
    }
};