每日OJ题_牛客_城市群数量_FloodFill_C++_Java

目录

牛客_城市群数量_BFS/并查集

题目解析

C++代码

Java代码

牛客_城市群数量_BFS/并查集

城市群数量_牛客题霸_牛客网 (nowcoder.com)

描述：

        给定一个 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);
            }
        }
    }
}