경로압축의 중요성...

 

경로 압축과 union by rank(또는 union by size)를 함께 사용하면,
전체 복잡도가 거의 상수 시간(O(α(n)), 여기서 α는 매우 느리게 증가하는 역아커만 함수)로 줄어들기 때문에 매우 효율적이다.

static int getParent(int n1) {
        if (parent[n1] == n1) {
            return n1;
        }
        return parent[n1] = getParent(parent[n1]);
    }

 

즉, 트리 탐색 깊이 줄여줘야 함

 

 

 

 

https://www.acmicpc.net/problem/10775

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int g,p;
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        g = Integer.parseInt(br.readLine());
        p = Integer.parseInt(br.readLine());
        parent = new int[g + 1];
        for (int i = 0; i < g + 1; i++) {
            parent[i] = i;
        }
        int ans = 0;
        for (int i = 0; i < p; i++) {
            int airplane = Integer.parseInt(br.readLine());
            int gate = getParent(airplane);
            if (gate != 0) {
                ans++;
                union(gate, gate - 1);
            } else break;
        }
        bw.write(ans + "");
        bw.flush();
        bw.close();
    }

    static int getParent(int n1) {
        if (parent[n1] == n1) {
            return n1;
        }
        return parent[n1] = getParent(parent[n1]);
    }

    static void union(int n1, int n2) {
        n1 = getParent(n1);
        n2 = getParent(n2);
        if (n1 < n2) {
            parent[n2] = n1;
        } else {
            parent[n1] = n2;
        }
    }
}