昨天看了sedgewick的alg in c 的第一章，主要介紹了個find-union 判斷聯通的算法，其實用到了并查集的知識
剛才偶然看見poj并查集的題集 就copy過來自己也寫寫看~~·
慢慢來~~ 寫完一道上一道~~
POJ 1182 食物鏈
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
還以為是最簡單的一道呢，被列在最前面，原來是擴展的應用，不是那么直接啊~
糾結了一會兒，看了解題報告才有思路。關鍵是在并查集的基礎上增加一個數組，維護其與根節點的關系；
詳情寫到注釋里面吧：
int A[100003][3];
int root[50005],k[50005];//root記錄節點所屬于的樹木id k記錄節點與根的關系0 同類1子是食物2子是天敵
int sz[50005];
int find(int x){
if(root[x]==x)return x;//如果是根則返回
else if(root[root[x]]==root[x])return root[x];//如果第一層，則返回
int father=root[x];
root[x]=find(father);//放到第一層，減少下次find時間，減小樹的高度
k[x]=(k[x]+k[father])%3;//由自己與根的關系以及父節點與根的關系推斷出新的自己與根的關系，實際上是為了解決union后的節點與根的關系 //因為union后，非根節點并沒有更新k，因此需要在此處處理更新
return root[x];
}
inline void Union(int x,int y,int kind){
int a=find(x);int b=find(y);
if(sz[a]>sz[b]){//判斷后決定，要把size小的放到size大的上去，優化作用不大
root[b]=a ; //b成為a的子樹
k[b]=(k[x]-k[y]+kind+3)%3;//要把b變成a的子樹，從a出發，到x，經過kind，到y，再到b ，可以得到kb的狀態改變公式
sz[a]+=sz[b];}
else{
if(kind==1)kind=2;
root[a]=b;
k[a]=(k[y]-k[x]+kind+3)%3;
sz[b]+=sz[a];
}
}
int main()
{
int N,d;
freopen("d:\\input.txt","r",stdin);
scanf("%d %d",&N,&d);
for(int i=1;i<=N;i++)sz[i]=1;
int cnt=0;
for(int s=1;s<=N;s++)root[s]=s;
int LIE=0;
int i=0;
while(i !=d) {
scanf("%d %d %d",&A[i][0],&A[i][1],&A[i][2]);
if(A[i][1]>N || A[i][2]>N ) {LIE++;i++;continue;}
if(A[i][0]==1){
if(find(A[i][1]) == find(A[i][2])){
if(k[A[i][1]]!=k[A[i][2]]) LIE++;
}
else Union(A[i][1],A[i][2],0);
}
else{
if( find(A[i][1])==find(A[i][2]) ){if(k[A[i][2]] != ( k[A[i][1]]+1)%3)LIE++;}
else Union(A[i][1],A[i][2],1);
}
i++;
}
cout<<LIE<<endl;
return 0;
}POJ 1611 The Suspects
http://acm.pku.edu.cn/JudgeOnline/problem?id=1611
int G[30005];
int sz[30005];
int Find(int x){
if(G[x]==x)return x;
else {
while(G[x]!=x){//half路徑壓縮~等下試試看全壓縮的效率~那樣就是遞歸調用啦
int t=G[x];
G[x]=G[t];
x=t;
}
return x;
}
}
void Union(int x,int y){
if(sz[x]<sz[y])swap(x,y);//把size小的弄到大的上面
G[y]=x;
sz[x]+=sz[y];
}
int main()
{
freopen("d:\\input.txt","r",stdin);
int N,M,num;
while(true){
scanf("%d %d",&N,&M);
if(N==0&&M==0)return 0;
for(int i=0;i<N;i++)G[i]=i,sz[i]=1;
for(int i=0;i<M;i++){
scanf("%d",&num);
int root,stu,x,y;
for(int j=0;j<num;j++){
scanf("%d",&stu);
if(j==0)root=Find(stu);//簡單的都和第一個合并
else{
root=Find(root);
x=Find(stu);if(root!=x)Union(root,x);
}
}
}
printf("%d\n",sz[Find(0)]);
}
}
POJ 2524 Ubiquitous Religions
又一道水題~~ 呵呵
不貼代碼了 和上面一道基本一樣~
http://acm.pku.edu.cn/JudgeOnline/problem?id=2524
POJ 1861
http://acm.pku.edu.cn/JudgeOnline/problem?id=1861
kruskal+并查集+half路徑壓縮
比較基礎的題
struct Edge{
int from;
int to;
int value;
}E[15000];
int A[1005];
int sz[2009];
bool comp(const Edge& a,const Edge& b){
return a.value<b.value;
}
using namespace std;
int Find(int x){
if(A[x]==x)return x;
else if(A[A[x]]==A[x]) return A[x];
int father;
while(A[x]!=x){
father=A[x];
A[x]=A[father];//把每一個路過的節點放到祖父下面去
x=father;
}
return x;
}
void Union(int x,int y){
if(sz[y]>sz[x])swap(x,y);//小的放到大的下面
sz[x]+=sz[y];
A[y]=x;
}
int main()
{
freopen("d:\\input.txt","r",stdin);
int N,M,num,x,y;
scanf("%d %d",&N,&M);
int cnt=0;
while(cnt<M) scanf("%d %d %d",&E[cnt].from,&E[cnt].to,&E[cnt].value),cnt++;
sort(E,E+M,comp);//從小到大選n-1條邊，如果起點和終點在一個集合則continue；else Union
for(int i=0;i<=N;i++)sz[i]=1,A[i]=i;
vector<int> ans(N-1);
int mst=0,MX=0;
for(int i=0;mst!=N-1;i++){
int x=Find(E[i].from);int y=Find(E[i].to);
if(x==y)continue;
Union(x,y);
ans[mst]=i;
mst++;
if(E[i].value>MX)MX=E[i].value;
}
printf("%d\n%d\n",MX,N-1);
for(int i=0;i<N-1;i++)
printf("%d %d\n",E[ans[i]].from,E[ans[i]].to);
}
POJ 1456 Supermarket
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
POJ 1733 Parity game
http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
hdu 3038 How Many Answers Are Wrong
http://acm.hdu.edu.cn/showproblem.php?pid=3038
POJ 1417 True Liars(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
POJ 2912 Rochambeau(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2912