并查集模板

1.并查集

const int MAXN = 1e5 + 5e2;
int bin[MAXN];
inline int find (int x) {
	return bin[x] == x ? x : (bin[x] = find(bin[x]); 
}
inline void merge(int a, int b) {
	int fa = find(a);
	int fb = find(b);
	if (fa != fb) {
		bin[fa] = fb;
	}
}

2.带权并查集

const int MAXN = 2e5 + 5e2;
int bin[MAXN], sum[MAXN];
int res = 0;
inline int find(int x) {
    if (x != bin[x]) {
        int temp = bin[x];
        bin[x] = find(bin[x]);
        sum[x] += sum[temp];
    }
    return bin[x];
}
inline void merge(int a, int b, int val) {
    int fa = find(a);
    int fb = find(b);
    if (fa != fb) {
        bin[fa] = fb;
        sum[fa] = - sum[a] + sum[b] + val; //合并后a到fa的权值会是反的，素以需要减去
    }
}