[정보올림피아드] 1863. 종료 (Union-find, 시간제한)

scanner로 입력받으면 시간 초과한다.

union으로 합칠 때 트리 깊이가 더 작은 것을 더 큰 것에 붙여줘야한다. 안 그러면 시간 초과난다.

(다른 애들을 검사할 때 깊이가 점점 더 깊어지기 때문에)

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

// 정올 1863 종료
public class Main {
	static int n,m;
	static int[] parent;
	static int[] depth;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String str=br.readLine();
		StringTokenizer st=new StringTokenizer(str);
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		parent=new int[n+1];
		depth=new int[n+1];
		for (int i = 1; i <=n; i++) {
			parent[i]=i;
			depth[i]=1;
		}
		for (int i = 0; i < m; i++) {
			str=br.readLine();
			st=new StringTokenizer(str);
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			union(a,b);
		}
		int cnt=0;
		for (int i = 1; i <=n; i++) {
			if(parent[i]==i) {
				cnt+=1;
			}
		}
//		System.out.println("depth"+Arrays.toString(depth));
		System.out.println(cnt);
	}
	private static int findSet(int x) {
		if(parent[x]==x) {
			return x;
		}
		return parent[x]=findSet(parent[x]);
	}
	
	private static void union(int x,int y) {
		x=findSet(x);
		y=findSet(y);

		if(depth[x]<depth[y]) {
			parent[x]=y;
			depth[y]+=depth[x];
		}
		else {
			parent[y]=x;
			if(depth[x]==depth[y]) {
				depth[x]++;
			}else {
				depth[x]+=depth[y];
			}
			
		}
		
	}
}