BOJ - 1717 집합의 표현

1717 집합의 표헌 : https://www.acmicpc.net/problem/1717

---

Problem

---

Solve

두 원소가 같은 집합에 있는지 여부를 판단하는 것을 보고 유니온 파인드 알고리즘을 떠올렸다.
0일 때 a,b의 그룹을 같은 그룹으로 묶어주고, 1일 때 a,b의 그룹이 동일한지 찾으면 된다.

유니온 파인드 : https://blog.naver.com/ndb796/221230967614

---

Code

public class 집합의표현 {
	static int[] group;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		group = new int[N+1];

		for(int i=0;i<=N;i++){
			group[i] = i;
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine(), " ");

			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if(type == 0){
            //두 원소의 집합 합침
				union(a, b);
			}else if(type == 1){
            //두 원소의 집합의 동일 여부
				if(isContains(a,b)){
					sb.append("YES");
				}else{
					sb.append("NO");
				}
				sb.append("\n");
			}
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static boolean isContains(int a, int b){
		a = find(a);
		b = find(b);

		return a==b;
	}

	static void union(int a, int b){
		a = find(a);
		b = find(b);

		//두 원소 중 집합의 값이 더 작은 것을 기준으로 집합을 표시한다.
		if(a>b){
			group[a] = b;
		}else{
			group[b] = a;
		}
	}

	static int find(int a){
		if(a == group[a]) return a;
		else return group[a] = find(group[a]);
	}
}

---

Result

---

Reference