java模板系列之并查集-hdu1232

题目是hdu 1232 https://vjudge.net/problem/HDU-1232

并查集中get和merge的时间复杂度都是反阿克曼函数，可近似看作为常数（5以内），故整个并查集的时间复杂度就是get和merage的调用次数

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.util.*;

public class Main {

    static int fa[];
    static int n,m;

    static void init(int n){
        for(int i=0;i<=n;i++){
            fa[i] = i;
        }
    }

    static int get(int x){
        if(x == fa[x]) return x;
        return fa[x] = get(fa[x]);
    }

    static void merge(int x,int y){
        int newx = get(x);
        int newy = get(y);
        fa[newx] = newy;
    }

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            n = input.nextInt();
            if(n == 0) break;
            m = input.nextInt();
            fa = new int[n+1];
            init(n);
            for(int i=0;i<m;i++){
                int from,to;
                from = input.nextInt();
                to = input.nextInt();
                merge(from,to);
            }
            boolean vis[] = new boolean[n+1];
            Arrays.fill(vis,false);
            int res = -1;
            for(int i=1;i<=n;i++){
                if (vis[get(i)] == false){
                    res++;
                    vis[get(i)] = true;
                }
            }
            System.out.println(res);
        }

    }




}