Union-Find

Union-Find란

그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

루트노드를 저장해놓은 parent배열을 이용하여 같은 집합에 속하는지 아닌지를 구별할 수 있습니다.

핵심 코드

// 최상위 노드를 가져오는 함수
int getParent(int x) {
	if (parent[x] == x) { // 부모와 자기자신이 같으면 리턴
		return x;
	}
	else {
		return parent[x] = getParent(parent[x]); // 경로압축
	}
}

// a와 b를 같은 집합으로 합치는 함수
void unionNode(int a, int b) { // 작은쪽으로 부모를 몰아줍니다. (a가 작아야함)
	if (a > b) { swap(a, b); } // a가 크면 a를 작게 만들어줍니다.
	 parent[getParent(b)] = getParent(a);// 작은 것이 부모가 되게 합니다.
}