[2022 1학기] 10주차 - 유니온-파인드

1. 유니온-파인드(union-find)란?

상호배타적집합(Disjoint-Set, 서로소 집합)을 표현할 때 사용하는 자료구조

MST(크루스칼)에 사용되는 알고리즘이다

여러 노드가 존재할 때, 두 노드를 같은 집합으로 묶고 같은 그래프에 속하는지 판별

 

2. 동작 원리

각 번호의 노드가 어떤 부모노드를 갖고 있는지 판별하고 

Find: 한 노드가 어느 집합에 포함되어 있는지 찾는 연산

Union: 노드 a가 포함된 집합과 노드 b가 포함된 집합을 합치는 연산

 

3. 코드

int N, M;
int parent[1000001];

int Find(int x) {
	if (parent[x] == x) {
		return x;
	}
	else{
		return parent[x] = Find(parent[x]);
    
        //return find[parent[x]]; //방법2

        //int y = find(parent[x]);  //방법3
        //parent[x] = y;
        //return y;
    	}
    
}


void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a == b) {
		return;
	}

	parent[b] = a;
}


int main() {

	scanf("%d %d", &N, &M);


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


	while (M--) {
		int select, a, b;

		scanf("%d %d %d", &select, &a, &b);

		if (select == 0) { //Union
			
			Union(a, b);
		
		}
		else { //Find
			a = Find(a);
			b = Find(b);

			if (a == b) {
				printf("YES\n");
			}
			else {
				printf("NO\n");
			}
			
		}
	
	}

	return 0;
}

 

 

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!