题目网址：http://poj.org/problem?id=1182
题意概述：看题目即可，不冗长。
此题中，把已知逻辑关系的点放到一个集合之中，用并查集处理。并查集中带的权值是“该点与父节点之间的逻辑关系”。
依次考察四个函数的写法，initial（初始化）没有特别之处，find时对权值的更新也很好理解，相当于是两个有向的箭头合并为一个箭头，judge没有变化，关键是merge，此时有三个有向箭头，并且其中一个箭头需要调整方向（当时没有注意到，wa吐）。
抽取一下精髓，对于并查集中的权值，其意义往往是“该点与其父结点的关系”，并且往往需要有某种“传递性”或者叫做“累加性”。
再丢出另外一个习题，同样是带权并查集。剧透：权值的意义是“该点下面的方块比父结点下面的方块多几个”。
题目网址：http://poj.org/problem?id=1988
给出两个题的代码：
T1:
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8
9 int N,K;
10 struct union_find{
11 static const int maxn=50005;
12 int pa[maxn],stk[maxn],top,sta[maxn];//sta表示点i在并查集中与其父亲的关系，0同类，1吃父亲，2被父亲吃
13 void initial(int n){ for(int i=1;i<=n;i++) pa[i]=i,sta[i]=0; }
14 int f(int x,int y){ return (x+y)%3; }//关系转换函数
15 int find(int x){
16 while(x!=pa[x]) stk[++top]=x,x=pa[x];
17 int last=0;
18 while(top){
19 int y=stk[top--];
20 sta[y]=f(last,sta[y]),last=sta[y];
21 pa[y]=x;
22 }
23 return x;
24 }
25 bool judge(int x,int y){ return find(x)==find(y); }
26 int G(int x){ find(x); return sta[x]; }//求得x与代表元之间的关系
27 int F(int x){ return (3-G(x))%3; }//对x于代表元之间的关系取反，用于调整向量的方向
28 void merge(int x,int y,int s){
29 int t1=F(x),t2=G(y);
30 x=find(x),y=find(y);
31 pa[x]=y,sta[x]=f(t1,f(s,t2));//注意合并的时候是处理了3个向量，pa[x]->x,x->y,y->pa[y]
32 }
33 }uf;
34
35 int main()
36 {
37 scanf("%d%d",&N,&K);
38 uf.initial(N);
39 int D,X,Y,ans=0;
40 for(int i=1;i<=K;i++){
41 scanf("%d%d%d",&D,&X,&Y);
42 if(X>N||Y>N||X==Y&&D==2) ans++;
43 else if(D==1){
44 if(uf.judge(X,Y)){ if(uf.G(X)!=uf.G(Y)) ans++; }
45 else uf.merge(X,Y,0);
46 }
47 else if(D==2){
48 if(uf.judge(X,Y)){
49 if(uf.f(uf.F(Y),uf.G(X))!=1) ans++;
50 }
51 else uf.merge(X,Y,1);
52 }
53 }
54 printf("%d\n",ans);
55 return 0;
56 }
View Code
T2:
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 using namespace std;
8
9 int P;
10 struct union_find{
11 static const int maxn=30005;
12 int pa[maxn],stk[maxn],top,add[maxn],sz[maxn];
13 void initial(int n){
14 for(int i=1;i<=n;i++) pa[i]=i,sz[i]=1,add[i]=0;
15 }
16 int find(int x){
17 while(x!=pa[x]) stk[++top]=x,x=pa[x];
18 int sum=add[x];
19 while(top){
20 int y=stk[top--];
21 add[y]+=sum,sum=add[y];
22 pa[y]=x;
23 }
24 return x;
25 }
26 bool judge(int x,int y){ return find(x)==find(y); }
27 void merge(int x,int y){
28 x=find(x),y=find(y);
29 add[x]+=sz[y],sz[y]+=sz[x],sz[x]=0;
30 pa[x]=y;
31 }
32 int COUNT(int x){ find(x); return add[x]; }
33 }uf;
34
35 void read(char &ch){
36 ch=getchar();
37 while(ch!='M'&&ch!='C') ch=getchar();
38 }
39 int main()
40 {
41 uf.initial(30000);
42 scanf("%d",&P);
43 char op; int x,y;
44 for(int i=1;i<=P;i++){
45 read(op);
46 if(op=='M'){
47 scanf("%d%d",&x,&y);
48 uf.merge(x,y);
49 }
50 else if(op=='C'){
51 scanf("%d",&x);
52 printf("%d\n",uf.COUNT(x));
53 }
54 }
55 return 0;
56 }
View Code