本文主要是介绍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;}
}
这篇关于leetcode 547.省份数量的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!