不务正业系列之pat解题: 1118. Birds in Forest (25)

[yooocen]

有两个用例超时，但是我觉得是java的问题，这题用到并查集

import java.util.Scanner;

public class Main {
    private int[] map = new int[10000];
    private int kinds = 0;
    private int query = 0;

    public void intput(Scanner sc){

        int numOfPicture = sc.nextInt();
        for(int i = 0 ; i < numOfPicture ; i++){
            int n = sc.nextInt();
            int fIndex = sc.nextInt();
            if(map[fIndex]==0){
                kinds++;
                map[fIndex] = fIndex;
            }
            for(int j = 1 ; j < n ; j++){
                int kindOfBird = sc.nextInt();
                if(map[kindOfBird]==0){
                    kinds++;
                    map[kindOfBird] = kindOfBird;
                }
                Union(fIndex,kindOfBird);
                fIndex = kindOfBird;
            }
        }
        query = sc.nextInt();
    }

    public int searchFather(int index){
//        if(map[index] == index){
//            return index;
//        } else {
//            int fatherIndex = map[index];
//            return searchFather(fatherIndex);
//        }
        int x = index;
        while (index!=map[index]){
            index=map[index];
        }
        while (x!=map[x]){
            int a = x;
            x = map[x];
            map[a] = index;
        }
        return x;
    }

    public void Union(int front , int current){
        int frontFather = searchFather(front);
        int crrentFather = searchFather(current);
        map[crrentFather] = frontFather;
    }

    public static void main(String[] args) {
        int [] root = new int[10000];
        Main test = new Main();
    Scanner sc = new Scanner(System.in);
//        System.out.println(birdOfps);
        test.intput(sc);

        int trees = 0;
        for(int i = 1 ; i <= test.kinds ; i ++){
            int fid = test.searchFather(i);
            if(fid!=0){
                root[fid]++;
                if(root[fid]==1){
                    trees++;
                }
            }
        }
        System.out.println(trees+" "+test.kinds);

        for(int i = 0 ; i < test.query; i++){
            int ii = sc.nextInt();
            int jj = sc.nextInt();
            if(test.searchFather(ii)==test.searchFather(jj)){
                System.out.println("Yes");
            }else {
                System.out.println("No");
            }
        }
    }
}