코드

Find 함수

int f(int i) {
	if (p[i] == i) return i;
	return p[i] = f(p[i]); //p 배열의 깊이를 줄일 수 있음
}

Merge 함수

void merge(int a, int b) {
	a = f(a), b = f(b);
	if (a != b) p[b] = a;
}

bool merge(int a, int b) {
	a = f(a), b = f(b);
	if(a == b) return false; //이미 같은 그룹
	p[b] = a;
	return true; //새로 묶음
}

관련 문제들

https://www.acmicpc.net/problem/1717