北大暑期学校-并查集和dfa gw disjoint set

暑期课《ACM/ICPC竞赛训信息学 信息学ZhouJuly15,21合并两个集2.查询一个元素在哪个集3.查询两个元素是否属于同一集July15, 并查集操作示 DisjointJuly15,4土算给集合编113416 113416 123456111411 111411July15, 土算给集合编123456113456113416113413111411Query–O(1);Merge–July15, 用树结构表示集abcdefabcdefabcdefabcdefabecdabecdfJuly15, abecfdabecf用树abecfdabecfabecdabecdfddJuly15, 用树结构表示集父亲。若元素i是树根，则Par[i]=i fJuly15, 用树结构表示集aadbecfJuly15, 用树结构表示集ababcdJuly15, 较小Rank的树连到较大Rank树的根部July15, NewLINK(x,Ifpar[y]Par[x]If

OldLINK(x,par[y]July15, GET_PAR(a)//求a的根节IfReturnReturnQuery(a,b)–ReturnMerge(a,b)–LINK(GET_PAR(a),GET_PAR(b)July15, 改进方法2路径压将GET_PAR中查找路径上的节点直接指向aabcdabcdJuly15,abcd改进方法2路径压NewIfPar[a]Return

OldIfReturnReturnJuly15, 复杂AmortizedcostofGET_PARoperationGET_PAR函数的平摊复杂度为

=0,if=1,if=2,if=3,if=4,if

.. 2 July15, 实际应实际应用路径压缩足矣，不要什么rankJuly15, 实际应intget_par(intu)ifpar[a]=return}intintquery(inta,intb)return}

voidmerge(inta,intb)par[get_par(a)]=}July15, POJ1611 n个学生分属m个团体，(0n30000m500一个学生可以属于多个团July15, POJ1611 n个学生分属m个团体，(0n30000m500一个学生可以属于多个团July15, POJ1611 Sample1002152992000

Sample411July15, POJ1611 #include<iostream>usingnamespacestd;constintMAX=30000;intn,m,k;intintintGetParent(int{//获取a的根,并把a的父节点改为if(parent[a]!=parent[a]=returnparent[a];

voidMerge(inta,int{intp1=GetParent(a);intp2=GetParent(b);if(p1==p2)total[p1]+=total[p2];parent[p2]=p1;}}POJ1611 intmain()if(n==0&&m==0)for(inti=0;i<n;++i){parent[i]=

total[i]=1;}for(inti=0;i<m;++i)

intfor(intj=1;j<k;++j)}}printf(“%d\n”,total[GetParent(0)]);//此处写parent[0]可否}return}POJ1611 intmain()if(n==0&&m==0)for(inti=0;i<n;++i){parent[i]=

total[i]=1;}for(inti=0;i<m;++i)

int

scanf("%d",&hfor(intj=1;j<k;++j)}}

printf(“%d\n”,total[GetParent(0)]);//此处写parent[0]可否}return}POJ1988Cube方块。方块编号1–N.有两种操作：Mxy示把方块x所在的堆，拿起来叠放Cx问方块x下面有多少个方July15, POJ1988Cube除了parent数组，还要开sum数组：记录每堆一共有多少方若parent[a]a,则sum[a]表示a所在的堆的udrund[iiJuly15,POJ1988Cube1234567812345678143143

1761761171176

143143POJ1988Cube432M343212127655CPOJ1988Cube4343266 C 55POJ1988Cube4671432467143255POJ1988Cube#include<iostream>#include<cstdio>constintMAX=intintGetParent(intif(parent[a]==returnintt=GetParent(parent[a]);under[a]+=under[parent[a]];parent[a]=t;return}POJ1988CubevoidMerge(inta,int intintpa=GetParent(a);intpb=GetParent(b);if(pa==pb)returnparent[pb]=parent[pb]pb,pb一定是原b所在堆最sum[pa]+=}POJ1988Cubeint{intfor(inti=0;i<MAX;++i)sum[i]=under[i]=parent[i]=}POJ1988Cubefor(inti=0;i<p;++i)char intif(s[0]=='M')}else}}

return}POJ1182食物1XY：表示X与Y2XY：表示X吃Y当前的话与前面的某些真的 POJ1182食物输入以下KD，X，Y，两数约束条1N50000，0K100000POJ1182食物S[X][Y1：表示X与YS[X][Y0：表示X与YS[X][Y1：表示X吃S[X][Y2：表示Y吃X若S[x][ys且S[x][y1，计数器加1复杂 0<=N<=50000，0<=K<=100000，杂度太进一步分（或m=0时的ab）之间的相对关系均已确b对a的相对关系才可以 解决方解决方点中该结点与父结点之间的关系。parentparent[i]表示i的父节解决方初始状态下，每个结点单独构成一棵读入a,b关系描述时的逻辑判若ra=rb，则可计算出r(a,b)=fr(a,rar(b,rb Exercise3ABug‟sPOJ2492ABug„s法一:深度优先遍只有:男->女，女->否则，找 二分图匹配，结束程法二:并查July15, OtherPOJ2524POJ