Union-Find 알고리즘

연결되어 있는 노드를 표현하기 위한 알고리즘.

연결되어있는 것중 가장 작은 값을 부모로 설정한다. 

해당 값을 부모로 가지고 있는 노드들이 연결되어있다고 보면 된다.

 

public class Main{
	// 부모노드 찾기
	public static int getParent(int arr[], int x) {
		if(arr[x] == x) 
			return x;
		return arr[x] = getParent(arr, arr[x]);
	}
	// 두 부모 노드 합치기
	public static void unionParent(int arr[], int a, int b) {
		a = getParent(arr, a);
		b = getParent(arr, b);
		if(a < b) {
			arr[b] = a;
		}else {
			arr[a] = b;
		}
	}
	
	// 같은 부모를 가지는지 확인, 노드가 연결되어있는지 확인
	public static boolean findParent(int arr[], int a, int b) {
		a = getParent(arr, a);
		b = getParent(arr, b);
		if(a == b)
			return true;
		else
			return false;
	}
    public static void main(String[] args) throws Exception {
    	Scanner sc = new Scanner(System.in);
    	int arr[] = {0, 1, 2, 3, 4, 5, 6, 7};
    	int a = sc.nextInt();
    	int b = sc.nextInt();
    	
    	// 노드 연결
    	unionParent(arr, 1, 2);
    	unionParent(arr, 1, 3);
    	unionParent(arr, 4, 5);
    	unionParent(arr, 5, 6);
    	unionParent(arr, 6, 7);
    	
    	for(int i=0; i<arr.length; i++) {
    		System.out.print(arr[i] + " ");
    	}
    	
    	// 연결여부 확인
    	System.out.println(findParent(arr, a, b));
    }
}

=================================================================================
1 5
0 1 1 1 4 4 4 4 false