加权维护集合/关系
例题（中二...
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define MAX 30000+99 5 int t; 6 int num[MAX], next[MAX]; 7 //num[i]表示i号战舰所处列中共有多少战舰, next[i] 表示i到所处列的第一个战舰中隔了有多少舰队 8 int fa[MAX]; 9 10 int find(int x) { 11 if(x == fa[x]) return fa[x]; 12 int fax = find(fa[x]); 13 next[x] += next[fa[x]];//在递归中将 x前面的战舰 和 x 的next值更新 14 //想想这为什么不能是fax 15 return fa[x] = fax; //在此说明：不用担心x后面的战舰，因为若是输入到了他们，在find函数中会更新到的 16 } 17 18 int main() { 19 for(int i = 1; i <= 30000; i++) fa[i] = i, num[i] = 1; 20 scanf("%d",&t); 21 char cmd; 22 int x,y,fax,fay; 23 for(int i = 1; i <= t; i++) { 24 scanf("%s%d%d", &cmd,&x,&y); 25 fax = find(x), fay = find(y); 26 if(cmd == 'M') { 27 next[fax] += num[fay];//此处都是对fa操作 28 // next[x]+=num[y]; 29 num[fay] += num[fax]; 30 fa[fax] = fay; 31 num[fax] = 0;//其实这里将fax列清0的操作不用写，因为不可能在往fax后面插入战舰了 32 } 33 if(cmd == 'C') { 34 if(fax != fay) printf("-1 "); 35 else { 36 printf("%d ", abs(next[x]-next[y])-1);//注意 37 } 38 } 39 } 40 return 0; 41 }
进阶题（其实博主解释的也不是很清楚，读者们可以自行查阅
食物链：
value[i] 表示 i到根结点的距离（0为同类，1表示根吃i，2表示i吃根）(可看做深度)，保证根在最上方
判断： 若x,y的根节点相同，则表示x,y确定过关系，这时，只需要判断它说的是不是对的
若x,y的根节点不同，则表示x,y没有确定关系（确定关系了的根节点都是同一个 ），按照题意（前面无语句与他相违背），为真话
把好多种（不多吧）情况列出来之后，防止为负的，还防止超界，所以下面的用 （。。。+3）%3
1. a == 1时 给出的x与y是同类
1） 若(根节点相同（fx == fy）): 判断
: if(x,y到他们根结点的距离不同（v[x] != v[y]）)，则自相矛盾 ,不成立，ans++。
else 则成立 。
2） 若(根节点不相同（fx ！= fy）)
/x与y之间没有边相连（fx!=fy） 即表示在这之前没有确定过x,y之间的关系
所以这条语句为真，并合并根节点（注意这里39行是以fy为根）
: fa[fx] = fy;
value[fx] = (value[y] - value[x] + 3) % 3 //注： 此时x,y 处在同一深度//这的value[x]是x到fx的距离
//防止为负的
2. a == 2时 给出的x吃y
1） 若(根节点相同（fx == fy）): 判断
//这时给出的x吃y为真话时，满足value[y] - value[x] = 1
: if（ (value[y])%3 ！= (value[x]+1)%3） ，为假，ans++
else 则成立
2） 若(根节点不相同（fx ！= fy）):
同上，没有确定关系，为真话，并合并根节点，确定关系（根节点以fy）
: fa[fx] =fy;
value[fx] = (value[y]- 1 -value[x] + 3) % 3
1 #include<cstdio> 2 const int MAX = 500000+9; 3 4 int n,k,a,x,y,ans; 5 int fa[MAX],val[MAX]; 6 7 int dad(int x) 8 { 9 if(fa[x]!=x) 10 { 11 int fx=fa[x]; 12 //注意：要先写fa[x] = father(fa[x]) ,因为还要将val更新一下，这个需要一直找父亲 13 fa[x]=dad(fa[x]); 14 val[x]=(val[x]+val[fx])%3; 15 return fa[x]; 16 } 17 return fa[x]; 18 } 19 20 int main() { 21 scanf("%d%d",&n,&k); 22 for(int i = 1; i <= n; i++) fa[i] = i; 23 for(int i = 1; i <= k; i++) { 24 scanf("%d%d%d",&a,&x,&y); 25 if(x>n || y>n) { 26 ans++; 27 continue; 28 } 29 int fx = dad(x), fy = dad(y); 30 if(a == 1) { 31 if(fx == fy) { 32 if(val[x] != val[y]) ans++; 33 } 34 else { 35 fa[fx] = fy; 36 val[fx] = (val[y] - val[x]+3)%3; 37 } 38 } 39 else {//x 吃 y 40 if(fx == fy) { 41 if((val[x] + 1) % 3 != (val[y]) % 3 ) 42 ans++; 43 } 44 else { 45 fa[fx] = fy; 46 val[fx] = (val[y] - val[x] - 1 + 3)%3; 47 } 48 } 49 } 50 printf("%d",ans); 51 }
其他题目：
ps： 最近并查集的题目都没有找到测评网站（尤其是jzoj的题目..）若写错，见谅，望提醒
题目大意
观众席每一行构成一个圆形，每个圆形由300个座位组成，对300个座位按照顺时针编号1到300,且可以认为有无数多行。现在比赛的组织者希望 观众进入场地的顺序可以更加的有趣，在门票上规定的不是每个人的座位， 而是与这个圈中某个人的相对位置，可以坐在任意一行。 门票上标示的形式如下：A B x 表示第B个人必须在A的顺时针方向x个位置（比如A坐在4号位子，x=2，则B必须坐在6号位子）。 现在你就作为志愿者在 入场口检票。如果拿到一张门票，与之前给定的矛盾，则被视为是假票， 如果无矛盾，视为真票。现在给定该行入场观众的顺序，以及他们手中的 门票，请问其中有多少假票？
数据范围
1<=n<=50,000，1<=m<=100,000
样例：10 10
1 2 150
3 4 200
1 5 270
2 6 200
6 5 80
4 7 150
8 9 100
4 8 50
1 7 100
9 2 100
分析：
因为要判断是否与之前的产生矛盾，想到了用并查集
注意： 两个人是可以坐同一个座位的（因为有无线个圈），即你只要判断一个人的相对位置是否改变即可
不用判断两个人是否在同一座位上
加权维护（距离）关系
#include<cstdio> #define MAX 50000+99 int fa[MAX]; int dis[MAX];//dis[i] 表示i到祖先节点的相对距离 int n,m,ans; int find(int x) { if(x == fa[x]) return fa[x]; int fax = find(fa[x]); dis[x] = (dis[fa[x]] + dis[fax])%300; return fa[x] = fax; } int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) fa[i] = i; int fax,fay,x,y,z; for(int i = 1; i <= m; i++) { scanf("%d%d%d",&x,&y,&z); fax = find(x), fay = find(y); if(fax != fay) {//这都是操控fa（因为find函数 fa[fax] = fay;//加入集合 （因为fay是祖宗，下面修改dis[fax] dis[fax] = (dis[x]+z-dis[y]+300)%300;//注意防负 } else if(dis[fax] != (dis[x]+z-dis[y]+300)%300) ans++; } printf("%d",ans); }
非加权维护集合/关系(扩展域维护？
例题： 关押罪犯
/*
关押罪犯：//维护集合
问把N个人都关到这两个房间里会产生的最小的最大冲突，影响力为多少
有贪心的思想： 希望最大的怒气值最小，就将怒气值由大到小排序，将怒气值大的拆开
分别放入两个房间（分的两个集合）， 再!!记录某人的敌人的代表元素!!
如果由大到小遍历得到的两个人的敌人在同一个集合，那么这两个人的怒气值即为ans
（因为必须把他们放在同一个房间（集合），如果不放在同一个房间，那么影响力反而会增大
*/
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN = 20000+9; 5 const int MAXM = 100000+9; 6 7 int n,m; 8 int fa[MAXN],dad[MAXN]; 9 10 int father(int x) { 11 if(x == fa[x]) return x; 12 return fa[x] = father(fa[x]); 13 } 14 15 struct node{ 16 int x,y,val; 17 bool operator < (const node &xx) const { 18 return val > xx.val ; 19 } 20 }e[MAXM]; 21 22 int main() { 23 scanf("%d%d",&n,&m); 24 for(int i = 1; i <= m; i++) { 25 scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val ); 26 } 27 sort(e+1,e+1+m); 28 // for(int i = 1; i <= m; i++) { 29 // printf("%d : %d %d %d ",i,e[i].x ,e[i].y ,e[i].val ); 30 // } 31 for(int i = 1; i <= n; i++) { 32 fa[i] = i; 33 } 34 35 for(int i = 1; i <= m+1; i++) {//i 循环到 m + 1 时便无冲突，会输出0 36 37 int fx = father(e[i].x ) , fy = father(e[i].y ); 38 int x = e[i].x , y = e[i].y ; 39 if(fa[fx] == fa[fy]) { 40 printf("%d",e[i].val ); 41 return 0; 42 } 43 else {//需要分开 44 if(!dad[x]) {//标记敌人 45 dad[x] = y; 46 } 47 else {//将dad[x]与 dad[x]的敌人x的敌人y 合并 48 fa[father(dad[x])] = fy; 49 } 50 if(!dad[y]) {//标记敌人 51 dad[y] = x; 52 } 53 else {//将dad[x]与 dad[x]的敌人x的敌人y 合并 54 fa[father(dad[y])] = fx; 55 } 56 } 57 } 58 }
例题2描述
题意： 给出N个人物之间的M条关系，可能互为朋友或敌人，现在朋友的朋友互为朋友，敌人的敌人也互为朋友，互为朋友的人构成一 个朋友集团，问一共有多少个朋友集团。
维护人物关系的典例
错误代码 ：
#include<cstdio>
#include<iostream>
using namespace std;
#define MAX 10000
int fa[MAX],ene[MAX];
int n,m;
int vis[MAX];
int find(int x) {
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) fa[i] = i;
int fax,fay,x,y;
char g;
for(int i = 1; i <= m; i++) {
scanf(" %c %d %d",&g,&x,&y);//输入字符的时候还是用cin吧 这里加了空格了
fax = find(x), fay = find(y);
if(g == 'F') {
fa[fax] = fay;
continue;
}
if(g == 'E') {
if(!ene[x]) {//标记敌人
ene[x] = y;
} else {//既然x有了敌人（即x所在集合有了敌人的代表元素），就将x的敌人 与 y合并
fa[find(ene[x])] = fay;
}
if(!ene[y]) {//同上
ene[y] = x;
} else {
fa[find(ene[y])] = fax;
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
fax = fa[i];
if(!vis[fax]) {
ans++;
vis[fax] = 1;
}
}
printf("%d",ans);
return 0;
}
/*
6 4
E 1 4
F 3 5
F 4 6
E 1 2
*/
倍增并查集裸题，将一伙人放到一个集合，a的敌人的编号为a+n，当两个人是敌人时，将双方放到对方敌人的集合里。然后查询1~N所属的集合中有多少种不同的集合
至于为什么能用倍增并查集呢？？？原因是情敌的情敌是我的朋友。这样子的关系就可以倍增了。如果并不知道情敌的情敌是不是我的朋友的话就不能用这个方法了。
#include<cstdio>
#define MAX 10000*2
int n,m;
int fa[MAX];
int vis[MAX];
int find(int x) {
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n<<1; i++) fa[i] = i;
char fax,fay,g,a,b;
for(int i = 1; i <= m; i++) {
scanf(" %c%d%d",&g, &a, &b);
if(g == 'F') {
fax = find(a), fay = find(b);
fa[fax] = fay;
} else {
fax = find(a), fay = find(b+n);
fa[fax] = fay;
fax = find(a+n), fay = find(b);
fa[fax] = fay;
}
}
int ans = 0;
for(int i = 1; i <= n; i++) vis[find(i)] = 1;
for(int i = 1; i <= (n<<1); i++)
if(vis[i]) {
ans++;
}
printf("%d",ans);
}