北大暑期學(xué)校-并查集和dfa gw disjoint set

暑期課《ACM/ICPC競(jìng)賽訓(xùn)信息學(xué) 信息學(xué)ZhouJuly15,21合并兩個(gè)集2.查詢一個(gè)元素在哪個(gè)集3.查詢兩個(gè)元素是否屬于同一集July15, 并查集操作示 DisjointJuly15,4土算給集合編113416 113416 123456111411 111411July15, 土算給集合編123456113456113416113413111411Query–O(1);Merge–July15, 用樹結(jié)構(gòu)表示集abcdefabcdefabcdefabcdefabecdabecdfJuly15, abecfdabecf用樹abecfdabecfabecdabecdfddJuly15, 用樹結(jié)構(gòu)表示集父親。若元素i是樹根，則Par[i]=i fJuly15, 用樹結(jié)構(gòu)表示集aadbecfJuly15, 用樹結(jié)構(gòu)表示集ababcdJuly15, 較小Rank的樹連到較大Rank樹的根部July15, NewLINK(x,Ifpar[y]Par[x]If

OldLINK(x,par[y]July15, GET_PAR(a)//求a的根節(jié)IfReturnReturnQuery(a,b)–ReturnMerge(a,b)–LINK(GET_PAR(a),GET_PAR(b)July15, 改進(jìn)方法2路徑壓將GET_PAR中查找路徑上的節(jié)點(diǎn)直接指向aabcdabcdJuly15,abcd改進(jìn)方法2路徑壓NewIfPar[a]Return

OldIfReturnReturnJuly15, 復(fù)雜AmortizedcostofGET_PARoperationGET_PAR函數(shù)的平攤復(fù)雜度為

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

.. 2 July15, 實(shí)際應(yīng)實(shí)際應(yīng)用路徑壓縮足矣，不要什么rankJuly15, 實(shí)際應(yīng)intget_par(intu)ifpar[a]=return}intintquery(inta,intb)return}

voidmerge(inta,intb)par[get_par(a)]=}July15, POJ1611 n個(gè)學(xué)生分屬m個(gè)團(tuán)體，(0n30000m500一個(gè)學(xué)生可以屬于多個(gè)團(tuán)July15, POJ1611 n個(gè)學(xué)生分屬m個(gè)團(tuán)體，(0n30000m500一個(gè)學(xué)生可以屬于多個(gè)團(tuán)July15, POJ1611 Sample1002152992000

Sample411July15, POJ1611 #include<iostream>usingnamespacestd;constintMAX=30000;intn,m,k;intintintGetParent(int{//獲取a的根,并把a(bǔ)的父節(jié)點(diǎn)改為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方塊。方塊編號(hào)1–N.有兩種操作：Mxy示把方塊x所在的堆，拿起來疊放Cx問方塊x下面有多少個(gè)方July15, POJ1988Cube除了parent數(shù)組，還要開sum數(shù)組：記錄每堆一共有多少方若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當(dāng)前的話與前面的某些真的 POJ1182食物輸入以下KD，X，Y，兩數(shù)約束條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，計(jì)數(shù)器加1復(fù)雜 0<=N<=50000，0<=K<=100000，雜度太進(jìn)一步分（或m=0時(shí)的ab）之間的相對(duì)關(guān)系均已確b對(duì)a的相對(duì)關(guān)系才可以 解決方解決方點(diǎn)中該結(jié)點(diǎn)與父結(jié)點(diǎn)之間的關(guān)系。parentparent[i]表示i的父節(jié)解決方初始狀態(tài)下，每個(gè)結(jié)點(diǎn)單獨(dú)構(gòu)成一棵讀入a,b關(guān)系描述時(shí)的邏輯判若ra=rb，則可計(jì)算出r(a,b)=fr(a,rar(b,rb Exercise3ABug?sPOJ2492ABug?s法一:深度優(yōu)先遍只有:男->女，女->否則，找 二分圖匹配，結(jié)束程法二:并查July15, OtherPOJ2524POJ