547. 省份数量
DFS
深度优先搜索的思路是很直观的。遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵 i s C o n n e c t e d isConnectedisConnected 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数
class Solution { public: int findCircleNum(vector<vector<int>> &isConnected) { int n = isConnected.size(); int res = 0; vector<bool> visited(n, false); for (int i = 0; i < n; i++) { if (!visited[i]) { DFS(isConnected, i, visited); res++; } } return res; } void DFS(vector<vector<int>> &isConnected, int me, vector<bool> &visited) { visited[me] = true; for (int other = 0; other < isConnected.size(); other++) { if (isConnected[me][other] && !visited[other]) { DFS(isConnected, other, visited); } } } };
