城市群数量

[编程题]城市群数量

热度指数：2796 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n 个节点的邻接矩阵 m。节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，但可以认为 a 与 c 相连，定义 a,b,c 是一个城市群。

矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。

请你找出共有多少个城市群。

数据范围： $1 \le n \le 200 \$ ，矩阵中只包含 $0 \$ 和 $1 \$

示例1

输入

[[1,1,0],[1,1,0],[0,0,1]]

输出

说明

1 2 相连，3 独立，因此是 3 个城市群。

示例2

输入

[[1,1,0,0],[1,1,1,0],[0,1,1,0],[0,0,0,1]]

输出

说明

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;
}

发表于 2023-01-10 16:24:11 回复(0)