LeetCode省份数量

题目要求：

有 n 一个城市，有的相互连接，有的不相连。如果城市 a 与城市 b 与城市直接相连 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 它是一个直接或间接相连的城市，不包括其他没有相连的城市。

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

返回矩阵中 省份 的数量。

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

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

解题思路：

参观的城市是1，总共有n = isConnected.size()个城市，从没拜访过的城市开始dfs

代码展示：

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

运行结果：