并查集总结

---

hdu 3038 How Many Answers Are Wrong
题目大意：有n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。

带权并查集的典例。

sum[i]表示i到根的权值

首先是查询

int Find(int u){
	if(fa[u] == u) return u;
	int rt = Find(fa[u]);
	sum[u] += sum[fa[u]];
	return (fa[u] = rt);
}

然后是合并

			if(x != y){
				fa[x] = y;
				sum[x] = - sum[a] + sum[b]  + c;
			}	
			else {
				if(c != sum[a] - sum[b]) ans++;//!!
			}

合并的时候要注意第6行的谁减谁，一定要用距根距离大的减距根距离小的。

需要注意的是对于连续的区间，用左开右闭（a-1，b）来表示。这样1—>3,4->5 就表示成了连续的 0->3,3->5

CodeForces 766D
题意：n个单词，m个条件，q次询问，每个条件是 a x y ，如果a是1，代表xy是同义词，否则是反义词。
判断这个条件是否与以前的冲突，如果不冲突则列为已知条件并输出yes，否则输出no。
每次询问，询问两个单词的关系，如果没有关系，输出3。

两种方法

1.维护 2 个数组，一个记录同义词，一个记录反义词。

对每个单词a，定义at[a]表示与a相反的一个单词，初始at[a]=0。对关系分类处理

（1）单词a与单词b相同

判断是否成立：当且仅当b不属于a所在的集合的相反集合，即find(b)!=find(at[find(a)])。

若成立：将b所在的集合合并至a所在的集合，再将at[b]所在的集合合并至at[a]所在的集合。

（2）单词a与单词b相反

判断是否成立：当且仅当b不属于a所在的集合，即find(b)!=find(a)。

若成立：将a所在的集合合并至at[b]所在的集合，将b所在的集合合并至at[a]所在的集合。

2.考虑种类并查集

在普通并查集的基础上加个relation，表示该单词与根的relation。0代表同义词，1代表反义词。（就是两个域）

然后处理压缩路径时，则a与新根节点的关系更新就为，a和现在结点的关系+这个结点与根结点的关系 mod 2

注意：初始化的时候将根设为自己的同时，应该将relation设为0（自己与自己是同义词）。

CodeForces 371D
题目大意：有几个从上到下摆起来的容器，有两种操作，1是往编号为i的容器里到x升水，如果这个容器满了，水会溢出到下一个容器。2是问第i个容器有多少水

每一次倒水的时候，如果一个容器满了，我们就可以把它相邻的连在一起，将下一个没有满的容器作为它的父亲，这样每次我们都可以很快找到那一个没满的容器

POJ-1182 食物链
题目描述 Description
动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。 　　
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 　　
有人用两种说法对这N个动物所构成的食物链关系进行描述： 　　
第一种说法是“1 X Y”，表示X和Y是同类。 　　
第二种说法是“2 X Y”，表示X吃Y。 　　
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 　　
1） 当前的话与前面的某些真的话冲突，就是假话； 　　
2） 当前的话中X或Y比N大，就是假话； 　　
3） 当前的话表示X吃X，就是假话。 　　
你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。
输入描述 Input Description
第一行是两个整数N和K，以一个空格分隔。 　　
以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。 　　
若D=1，则表示X和Y是同类。 　　
若D=2，则表示X吃Y。
输出描述 Output Description
只有一个整数，表示假话的数目。

种类食物链，此题因为满足环可以用relation来维护，也可以用并查集+拓展域来维护（两者本质相同，后者的空间复杂度常数大一点，但容易理解）。

1到n为同类域，n + 1 到 2 * n 为吃域，2 * n + 1 到 3 * n 为天敌域（被吃域）

int Find(int u){
	return (fa[u] == u) ? u : fa[u] = Find(fa[u]);
}
void Union(int u,int v){
	int xx = Find(u);int yy = Find(v);
	if(xx != yy) fa[xx] = yy;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i = 1; i <= 3 * n; ++i) fa[i] = i;//!!
	for(int i = 1; i <= k; ++i){
		scanf("%d%d%d",&op,&x,&y);
		if(x > n || y > n) ans++;
		else if(op == 1){
			if(Find(x) == Find(y + n) || Find(x + n) == Find(y))	ans++;
			else {
				Union(x,y);
				Union(x + n,y + n);
				Union(x + 2 * n,y + 2 * n);
			}
		}
		else{
			if(Find(x) == Find(y) || Find(x) == Find(y + n)) ans++;
			else{
				Union(x,y + 2 * n);
				Union(x + n,y);
				Union(x + 2 * n,y + n);
			}
		}
	}
	printf("%d\n",ans);	
	return 0;
}

注意最后写完程序一定要把题目上的所有不满足的情况带进去，检查是否有遗漏。