目录
牛客_城市群数量_BFS/并查集
描述:
给定一个 n 个节点的邻接矩阵 m。 节点定义为城市,如果 a 城市与 b 城市相连, b 与 c 城市相连,尽管 a 与 c 并不直接相连,但可以认为 a 与 c 相连,定义 a,b,c 是一个城市群。
矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,否则表示不相连。
请你找出共有多少个城市群。
题目解析
经典 floodfill 算法,可以用 dfs 或者 bfs 或并查集解决。
C++代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param m int整型vector<vector<>>
* @return int整型
*/
int citys(vector<vector<int> >& m) {
int n1 = m.size(), n2= m[0].size();
vector<int> arr(n1, -1);
auto findRoot = [&](int x)
{
while(arr[x] != -1)
{
x = arr[x];
}
return x;
};
for(int i = 0; i < n1; ++i)
{
for(int j = 0; j < n2; ++j)
{
if(m[i][j] == 1)
{
int x1 = findRoot(i);
int x2 = findRoot(j);
if(x1 != x2) // x2合到x1
{
arr[x1] = arr[x2]; // 写OJ时少了这句,但也能过
arr[x2] = x1;
}
}
}
}
int res = 0;
for(auto& e : arr)
{
if(e == -1)
++res;
}
return res;
}
};
Java代码
import java.util.*;
public class Solution
{
int n;
boolean[] vis = new boolean[210];
public int citys (ArrayList<ArrayList<Integer>> m)
{
n = m.size();
int ret = 0;
for(int i = 0; i < n; i++)
{
if(vis[i] == false)
{
ret++;
dfs(m, i);
}
}
return ret;
}
public void dfs(ArrayList<ArrayList<Integer>> m, int pos)
{
vis[pos] = true;
for(int i = 0; i < n; i++)
{
if(m.get(pos).get(i) == 1 && vis[i] == false)
{
dfs(m, i);
}
}
}
}
标签:arr,Java,OJ,int,FloodFill,++,x2,x1,城市群
From: https://blog.csdn.net/GRrtx/article/details/143167636