서로소

1. 서로소

   서로소 집합은 공통 원소가 없는 집합을 의미한다.
   예를들어 {1,2} 와 {3,5}는 공통 원소가 없으므로 서로소집합이다.

2. unionset, findset

   unionset은 원소간의 연결관계를 정의한다. 부모노드와 자식노드.
   findset은 해당 원소의 부모를 찾는 연산을 한다.

3. swea 서로소```

import java.util.Scanner;

public class swea서로소 {

static int[] parent;
static int n,m;

public static void main(String[] args) {

	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	for(int tc=1; tc<=t; tc++) {
		n = sc.nextInt();
		m = sc.nextInt();
		parent = new int[n+1];
        // 초기에 자기자신을 부모로 정하는 make연산을 수행한다.
		make();
		System.out.print("#"+tc+" ");
		for(int i=0; i<m; i++) {
        	// 0 : union 1 : find
			int k = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			if(k == 0) {
				unionset(a,b);
			}else if(k == 1){
				if(findset(a) == findset(b)) System.out.print(1);
				else System.out.print(0);
			}
		}
		System.out.println();
	}
}

private static boolean unionset(int a, int b) {
	int aRoot = findset(a);
	int bRoot = findset(b);
	
	if(aRoot == bRoot) return false;
	// 작은 값을 루트로 정한다.
	if(aRoot<bRoot) parent[bRoot] = aRoot;
	else parent[aRoot] = bRoot;
	return true;
}

private static int findset(int x) {
	// 자기 자신이 부모이면 자신을 리턴한다.
	if(parent[x] == x) return x;
    // 아니면 재귀호출로 부모를 찾아 리턴한다.
	return findset(parent[x]);
}
// 초기 자기자신을 부모로하도록.
static void make() {
	for(int i =0; i<n; i++) {
		parent[i] = i;
	}
}

}