今天练习带权并查集

题1 ：Poj 1703

题意及算法分析：

如果a和b在一棵树上，则他们之间有关系，如果dis[a]与dis[b]同为0 或 1，则是同一个帮派，否则是不同的帮派，如果不在一棵树上，则状态不明确。

AC代码：

#include <cstdio>
#include <cstring>

const int maxn = 1e5 + 5;
int n, m, t, p[maxn], dis[maxn];

void init(){
	for(int i = 1;i <= n;i++){
		p[i] = i;
		dis[i] = 0;
	}
}

int find(int x){
	if(x == p[x])
		return x;
	int r = p[x]; p[x] = find(p[x]);
	dis[x] = (dis[x] + dis[r]) % 2;
	return p[x];
}

void merge(int x, int y){
	int px = find(x), py = find(y);
	if(px != py){
		p[px] = py;
		dis[px] = (dis[y] - dis[x] + 1) % 2;
	}
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&m);
		init();
		while(m--){
			char ch;
			int a, b;
			getchar();
			scanf("%c %d %d",&ch,&a,&b);
			if('D' == ch)
				merge(a, b);
			else{
				if(find(a) == find(b)){
					if(dis[a] == dis[b])
						printf("In the same gang.\n");
					else
						printf("In different gangs.\n");
				}
				else
					printf("Not sure yet.\n");
			}
		}
	}
	return 0;
}

题二：洛谷 2024 经典题：食物链

题意及算法分析：

有三个种类，则dis(x, y)分三类：
0：他们是同类
1：x吃y
2：x被y吃

这样分类有个好处：如果是同类：cmd = 1(1 - 1 = 0)，x被y吃：cmd = 2(2 - 1 = 1)
这样就可以得到：x与y的状态可以由cmd直接得出。

最初的权值：

因为最开始，自己和自己当然是一类生物，所以初始化的时候都是0（同类）

Find中的权值更新：

因为我们最终合并两棵树是合并他们的根，于是要得到dis(x, rx)
dis(x, rx) = (dis(x, rx) + dis(rx, rx)) % 3
也就是：dis[x] = (dis[x] + dis[r]) % 3

Union的权值更新：

我们规定更新的方向：p[px] = py
也就是把py当作新的树根，把px接到py的孩子处
因为我更新的对象是x和y，所以需要通过关系：dis(x, y)来更新dis(rx, ry)
我们已经根据上面的讲述，得到dis(x, y) = cmd - 1
x->rx, y->ry, rx->ry
根据这个向量关系可以得到：
dis(rx, ry) = dis(x, y) + dis(x, rx) - dis(y, ry)
所以代码就是：
dis[px] = (cmd - 1 + dis[x] - dis[y] + 3) % 3
这里加3的原因是维护非负整数

AC代码：

#include <cstdio>

const int maxn = 5e4 + 5;
int n, k, p[maxn], dis[maxn], ans;

int find(int x){
	if(x == p[x])	return x;
	int r = p[x]; p[x] = find(p[x]);
	dis[x] = (dis[x] + dis[r]) % 3;
	return p[x];
}

void merge(int type, int x, int y){
	int px = find(x), py = find(y);
	if(px != py){
		p[px] = py;
		dis[px] = (type - 1 + dis[y] - dis[x] + 3) % 3;
	}
}

int main(){
	scanf("%d %d",&n, &k);
	for(int i = 1;i <= n;i++)	p[i] = i, dis[i] = 0;
	while(k--){
		int cmd, a, b;
		scanf("%d %d %d",&cmd, &a, &b);
		if(a > n || b > n || (2 == cmd && a == b))
			ans++;
		else if(find(a) == find(b)){
			if(1 == cmd && dis[a] != dis[b])
				ans++;
			if(2 == cmd && dis[a] != (dis[b] + 1) % 3)
				ans++;
		}
		else
			merge(cmd, a, b);
	}
	printf("%d", ans);
	return 0;
}