leetcode 547.省份数量

思路：dfs

或者这道题用bfs也是可以的。

这道题有点迷惑性，这里的数组给的是无向图的数组，而并不是地图，这里需要着重注意一下。

而后，这里的状态数组st没必要是二维的，我们并不会去遍历所给的数组，这是没有意义的，我们只需要从这个数组中提取出来哪些城市有连接即可。

剩下的就是连通块的思想了。连通块前面已经写过很多了，大家可以去前面的博客看一下。

对于每一个编号的城市，在遍历的时候都进行标记，然后再去判断和其他城市有没有联系；如果有，就换到下一个城市里面，继续dfs；没有的话继续循环，这样就遍历完一个“省份”了，也就是一个连通块，不要忘记计数。

上代码：

class Solution {int []st=new int[210];int n;public void dfs(int x,int[][]s){if(x>=n)return;for(int i=0;i<n;i++){if(st[i]==0&&s[x][i]==1){st[i]=1;dfs(i,s);}}}public int findCircleNum(int[][] isConnected) {n=isConnected.length;int counts=0;for(int i=0;i<n;i++){if(st[i]==0){st[i]=1;dfs(i,isConnected);counts++;}}return counts;}
}