hyeoneee's blog

대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.

상호 배타적 집합(Disjoint-set)이라고도 합니다.

여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

즉, 그래프에서 같은 그룹에 속하는가? 를 물어볼 수 있는 알고리즘이다.

혹은 그룹을 합치거나

1. 초기화 ( make set)

자기자신을 부모로 갖도록 초기화 해준다.

int[] parent = new int[N+1];
for(int i = 0 ; i <= N ; i ++){
	parent[i] = i;
}

2. find

int find(int a){
	if(a == parent[a]) return a;
	return parent[a] = find(parent[a]); // 경로 압축

}

시간복잡도 O(N)

원래 return 부가 

return find(parent[a]) 인데 

return parent[a] = find(parent[a]) 로 경로 압축을 해주었다. 한번에 가기~!

3. union

void union(int a, int b){
	a = find(a);
	b = find(b);
	
	if(a != b){
		//항상 더 작은수로 부모를 넣어준다.
		if(a > b){ // a가 항상 작은수가 되도록 만듦
              int tmp = a;
              a = b;
              b = tmp;
        }
        parent[b] = a;
	}
}

4. 문제 풀기

1. 계속 합쳐지는 패턴 
2. 계속 분리되는 패턴 
 - 질문의 역순으로 답을 내야함 

  => 질문을 미리 저장해두고, 질문의 역순으로 답을 낸다. 

  
3. 그룹의 멤버의 수 
4. 유효/무효 값 분리