Disjoint Set(서로수 집합)

Disjoint Set : 디스조인트 셋 ? 

 

서로수집합은 한개의 집합으로는 성립되지 않고 집합이 여러개있을때 서로서로 공통적인 원소가 없어 모든 집합의 교집합은 공집합( Φ )이 된다는 말이다.

 

 

서로수 집합도 집합이니 집합 연산이 필요한데 서로수집합은 서로 공통원소가 없으니 차집합, 교집합은 의미가 없다.

차집합 교집합을 해봤자 다 공집합이기 때문이다.

따라서 합집합만 있으면 될것 같은데 서로수집합에서 합집합을 찾는 것을 disjoint set - 유니온(Union) 이라 하고

각 원소에가 트리의 어떤 루트노드에 연결되어 있는지 그 루트를 찾는 연산을 disjoint set - 파인드(Find) 라 부른다.

 

 

초기에 각 노드는 자기 자신을 루트 노드로 가진다.

for(int i = 1; i <= n; i++){
	parent[i] = i;
}

 

find()를 통해 반환되는 값은 주로 그 집합을 대표하는 값이 된다. 즉 루트노드가 된다.

public static int find(int u) { 
	if( u == parent[u] ) {
    	return u;
    }
    return parent[u] = find(parent[u]);
}

 

public static void merge(int u, int v) {
	u = find(v);
    v = find(v);
    
    if(u == v) {
    	return ;
    }
    
    parent[u] = v;
	
}