牛客网练习赛24B凤凰

题目链接

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

凤凰于飞，翙翙其羽，亦集爰止。凤凰于飞，翙翙其羽，亦集爰止。
《诗经·卷阿》
传说，凤凰是百鸟之王。有一天，凤凰要召开百鸟大会，百鸟国是一个由n个节点组成的树，每个节点有一只鸟，开会的节点定在1号节点。每只鸟可以花费1s通过一条边，由于每根树枝(边)的载重有限，只允许一只鸟同时通过。作为会议的策划师，HtBest想知道百鸟国的所有鸟在1点集合最少需要多少秒。

输入描述:
第一行有一个正整数n，表示百鸟国节点个数。
接下来n-1行，第i行两个正整数ai,bi用空格隔开，表示树上节点ai,bi之间有一条边。
输出描述:
第一行一个整数，表示集合最少需要的时间。
示例1
输入

3
1 2
2 3

输出

2

示例2
输入

3
1 2
1 3

输出

1

示例3
输入

4
1 2
2 3
2 4

输出

3

备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

---

该题为只需要计算根节点的直接子树中最大的节点数即可，所以可以用并查集进行分类
由于数据量较大，不能用scanner输入，这里采用BufferedReader读入（我的并查集入门题）
ac代码

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(sc.readLine());
        int bc[] = new int [1000005];
        while(--n>0) {
            String s[] = sc.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            if(a!= 1&&b!=1) {
                u(a,b,bc);
            }
        }
        int max = -1;
        max = max(bc);
        System.out.println(-max);
    
    }

    private static int max(int[] bc) {
        int max=0;
        for(int i = 0;i<=1000000;i++) &#123;
            if(max>bc[i]) &#123;
                max = bc[i];
            &#125;
        &#125;
        return max;
    &#125;
    
    private static int find(int a, int bc[]) &#123;
        if(bc[a] == 0) &#123;
            bc[a] = -1;
            return a;
        &#125;else if(bc[a]<0) &#123;
            return a;
        &#125;else &#123;
            return find(bc[a],bc);
        &#125;
    &#125;
    private static void u(int a, int b, int bc[]) &#123;
        int ra = find(a, bc);
        int rb = find(b, bc);
        if(ra != rb) &#123;
            if(bc[ra]<bc[rb]) &#123;
                bc[ra] = bc[ra]+bc[rb];
                bc[rb] = ra;
            &#125;else &#123;
                bc[rb] = bc[ra]+bc[rb];
                bc[ra] = rb;
            &#125;
        &#125;
    &#125;

&#125;