牛客网真题-95-紧急疏散-京东

查找子树的结点数量
bfs

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException{
        BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
        String s = buff.readLine();
        int n = Integer.parseInt(s);
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();//邻接表
        ArrayList<Integer> arr = new ArrayList<>();//根结点的子节点
        for(int i = 1; i <= n; i++){
            map.put(i, new ArrayList<>());
        }
        while (buff.ready()) {
            int[] s1 = Arrays.stream(buff.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            map.get(s1[0]).add(s1[1]);
            map.get(s1[1]).add(s1[0]);
            if(s1[0] == 1){
                arr.add(s1[1]);
            }
            if(s1[1] == 1){
                arr.add(s1[0]);
            }
        }

        //BFS
        int[] visit = new int[n + 1];
        visit[1] = 1;
        int sum = 0;
        for(int i = 0; i < arr.size(); i++){
            int node = arr.get(i), sumTemp = 0;
            visit[node] = 1;
            Queue<Integer> queue = new LinkedList<>();
            queue.add(node);
            while (!queue.isEmpty()) {
                sumTemp++;
                ArrayList<Integer> arrayList = map.get(queue.poll());
                for(int j = 0; j < arrayList.size(); j++){
                    if(visit[arrayList.get(j)] == 0){
                        queue.add(arrayList.get(j));
                        visit[arrayList.get(j)] = 1;
                    }
                }
            }
            sum = Math.max(sum, sumTemp);
        }
        System.out.println(sum);
    }
}