给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。
数据范围: , 矩阵中只包含和
[[1,1,0],[1,1,0],[0,0,1]]
2
1 2 相连,3 独立,因此是 3 个城市群。
[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]
2
1 , 2相连 ;2 ,3相连,4独立,因此是 1,2,3 属于一个城市群,4属于一个城市群。
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param m int整型二维数组 * @param mRowLen int m数组行数 * @param mColLen int* m数组列数 * @return int整型 */ void dfs(int** m, int mr, int mc,int i){ for(int j=0;j<mr;j++){ if(m[i][j]==1){ m[i][j]=0; m[j][i]=0; dfs(m,mr,mc,j); } } } int citys(int** m, int mRowLen, int* mColLen ) { // write code here int count=0; for(int i=0;i<mRowLen;i++){ for(int j=0;j<*mColLen;j++){ if(m[i][j]==1){ count++; m[i][j]=0; m[j][i]=0; dfs(m,mRowLen,*mColLen,i); dfs(m,mRowLen,*mColLen,j); } } } return count; }