并查集学习

普通并查集

用途：维护一个集合的连通性
不用多说，下面的才是重点

扩展域并查集

用途：维护两个以上的集合的连通性。
经典 例题
对于这个题，我们可以把人分成两个域：朋友域（\(1\) ~ \(n\)）和敌人域（\(n+1\) ~ \(2n\)）

1. 如果 \(u,v\) 是朋友，直接合并 \(u,v\)。
2. 如果 \(u,v\) 是敌人，那么 \(u\) 和 \(v\) 映射到敌人域中的 \(v+n\) 一定是朋友，所以合并 \(u\)，\(v+n\)。（\(u+v\) 和 \(v\) 同理）
   最后统计一下连通块的个数。

# include <bits/stdc++.h> 
using namespace std; 
typedef long long ll; 
// # define int long long 
# define lc u << 1
# define rc u << 1 | 1 
# define fi first
# define se second
inline int read ()
{
    int w = 1, s = 0;
    char c = getchar ();
    for (; c < '0' || c > '9'; w *= (c == '-') ? -1 : 1, c = getchar ());
    for (; c >= '0' && c <= '9'; s = 10 * s + (c - '0'), c = getchar ());
    return s * w;
}
const int N = 2005;

int n, m;
int fa[N];
int find_fa (int u) { return u == fa[u] ? u : fa[u] = find_fa (fa[u]); }
signed main ()
{
//	freopen ("test.in", "r", stdin);
//	freopen ("test.out", "w", stdout);	
	n = read (), m = read ();
	for (int i = 1; i <= n * 2; i ++ ) fa[i] = i;
	while (m -- )
	{
		char op; int u, v; scanf (" %c%d%d", &op, &u, &v);
		if (op == 'F') fa[find_fa (u)] = find_fa (v);
		else
		{
            fa[find_fa (u + n)] = find_fa (v);
            fa[find_fa (v + n)] = find_fa (u);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
    	if (i == fa[i])
    		cnt ++ ;
	}
	printf ("%d\n", cnt);
	return 0;
}

带权并查集

用途：可以在并查集的边上定义某种权值以及这种权值在路径压缩时产生的计算。
一般使用的是 \(d_x\) 表示 \(x\) 到根的距离。

int find_fa (int u)
{
	if (u == fa[u]) return u;
	int v = find_fa (fa[u]);
	d[u] = d[u] + d[fa[u]];
	return fa[u] = v;
}