서로 두 다른 원소가 같은 집합에 포함되어 있는지 확인할 수 있는 알고리즘이다.
유니온(합집합), 파인드(찾기) 함수로 이루어져 있다.
public static int find(int x){
if(parent[x]==x){
return x;
}
parent[x] =find(parent[x]);
return parent[x] ;
}
public static void union(int x, int y){
if(x > y){
int tmp = x;
x = y;
y = tmp;
}
// x 가 작음
int xRoot = find(x);
int yRoot = find(y);
if(xRoot == yRoot){
return ;
}
parent[yRoot] = xRoot;
}
유니온 파인드를 개념적으로 이해하긴 쉽지만 중간에 놓치면 안될 중요한 포인트가있다.
바로 find 함수에서 경로압축에 따라 시간복잡도 차이가 log(n) 과 n으로 큰 차이가 난다는 것이다.
public static int find(int x){
if(parent[x]==x){
return x;
}
parent[x] =find(parent[x]);
return parent[x] ;
}
public static int find(int x){
if(parent[x]==x){
return x;
}
return find(parent[x]);
}
위 코드는 경로압축, 아래는 그냥 코드이다.
경로 압축을 했을땐 부모에 실제 부모가 아닌 가장 높은 root 부모로 저장하고 리턴하게 된다.
이므로써 중복연산을 줄이고 시간복잡도를 개선할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int[] parent ;
public static int find(int x){
if(parent[x]==x){
return x;
}
parent[x] =find(parent[x]);
return parent[x] ;
}
public static void union(int x, int y){
if(x > y){
int tmp = x;
x = y;
y = tmp;
}
// x 가 작음
int xRoot = find(x);
int yRoot = find(y);
if(xRoot == yRoot){
return ;
}
parent[yRoot] = xRoot;
}
public static void main(String[] args) throws IOException {
String[] inp = br.readLine().split(" ");
int n = Integer.parseInt(inp[0]);
int m = Integer.parseInt(inp[1]);
parent = new int[n+1]; // 1인덱싱
for(int i=0;i<n;i++){
parent[i+1]=i+1;
}
// n m
for(int i=0;i<m;i++){
inp = br.readLine().split(" ");
int cmd = Integer.parseInt(inp[0]);
int a = Integer.parseInt(inp[1]);
int b = Integer.parseInt(inp[2]);
if(cmd==0){
union(a,b);
}else{
if(find(a)==find(b)){
bw.write("YES\n");
}
else{
bw.write("NO\n");
}
}
}
bw.flush();
}
}