[분류]
- 서로소 집합
[문제링크]
[요구사항]
- 각 index를 집합원소로 가지고 있는 노드들에 대하여 합집합 했을 때 같은 집합에 속하는지 알아내기
[풀이]
- union find를 그대로 구현하여 문제를 해결할 수 있다.
- 핵심은 union을 할 때 rank가 높은 쪽으로 붙이는 최적화 작업을 하는 것이다.
[코드]
//baekjoon_1717_집합의 표현
import java.io.*;
import java.lang.*;
public class Main {
static int n, m;
static int parent[];
static int rank[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
parent = new int[n+1];
rank = new int[n+1];
for(int i=0;i<n+1;i++){
parent[i]=i;
rank[i]=0;
}//부모는 모두 자기 자신으로 초기화
for(int i=0;i<m;i++){
s = br.readLine().split(" ");
int stat = Integer.parseInt(s[0]);
int a = Integer.parseInt(s[1]);
int b = Integer.parseInt(s[2]);
if(stat==0){
union(a,b);
}else{
if(isSame(a,b)) System.out.println("YES");
else System.out.println("NO");
}
}
}
public static void union(int x, int y){
x = find(x);
y = find(y);
if(x==y)
return;
if(rank[x]<rank[y]){
parent[x]=y;
}else if(rank[x]>rank[y]){
parent[y]=x;
}else{
parent[x]=y;
rank[y]++;
}
}
public static int find(int x){//find하면서 거치는 노드들의 부모를 모두 최상위 노드로 변경
if(parent[x]==x){
return x;
}
return parent[x]=find(parent[x]);
}
public static boolean isSame(int x, int y){
x=find(x);
y=find(y);
if(parent[x]==parent[y]) return true;
return false;
}
}
[통과여부]
[느낀점]
서로소 집합 역시 오랜만에 풀어봐서 다시 어떻게 푸는지 기억할 겸 풀어보았는데 원리는 아주 간단하였다.