disjoint set (union find) 자료구조

dsu.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define MAXN 50020

// disjoint set (DSU)
int parent[MAXN];
// rank를 뜻함
int depth[MAXN];

//find 함수
int root(int a) {
	int p = a;
	while (p != parent[p])
		p = parent[p];
	parent[a] = p;
	return p;
}
//같은 set에 포함되어있는지를 리턴
bool same(int a, int b) {
	return root(a) == root(b);
}
//union 함수
void unite(int a, int b) {
	a = root(a);
	b = root(b);
	if (a == b) return;
	if (depth[a] < depth[b]) {
		parent[a] = b;
	}
	else {
		parent[b] = a;
		if (depth[a] == depth[b])
			depth[b]++;
	}
}
void init(int N) {
	for (int i = 0; i < N; i++) {
		parent[i] = i;
		depth[i] = 0;
	}
}
int main() {
	int n;
	scanf("%d", &n);
	init(n);
	return 0;
}