[백준] 10775 공항 [자바]

 

---

https://mygumi.tistory.com/245

백준 10775번 공항 :: 마이구미

https://brenden.tistory.com/33

[알고리즘] 유니온 파인드 (Union-Find)

 

 

---

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

public class Main {
	static int G,P;
	static int[] parent;
	static boolean no_add = false;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		G = Integer.parseInt(br.readLine());
 		P = Integer.parseInt(br.readLine());
 		parent = new int[G+1];
 		int result = 0;
 		for(int i = 0; i <= G; i++) {
 			parent[i] = i;
 		}
 		for(int i = 0; i < P; i++) {
 			int temp = Integer.parseInt(br.readLine());
 			union(temp-1, temp);
 			if(!no_add)
 				result++;
 		}
 		System.out.println(result);
 	}
 	static int find(int x) {
 		//자기 자신을 바라보면 리턴
 		if(x == parent[x])
 			return x;
 		return parent[x] = find(parent[x]);
 	}
 	static int union(int x, int y) {
 		if(x == -1) {
 			no_add = true;
 			return 0;
 		}
 		x = find(x); //받은값 - 1
 		y = find(y); //받은값
 		if(x == y) {
 			parent[y] = union(x-1, x);
 		}
 		if(x != y) {
 			parent[y] = x; //받은값의 부모는 받은값 - 1의 부모(자기 자신일 수 있다)
 		}
 		return parent[y];
 	}
}