The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

并查集学习小节(POJ版)

什么是并查集呢,我相信大家都已经很熟悉了,在这里我就不再赘述。写这篇文章的主要目的不是新手教学,而是为了借POJ上相关的题目,全面的总结一下并查集问题和它的各个变种。

POJ 1611 The Suspects
题目大意:有n个学生(标号为0 to n-1),m个学生社团,给出每个社团里所有学生的标号,并假设0号学生患有SARS(社团里只要用一个学生患病,则整个社团里的学生都会被隔离),问最后一共会有多少学生被隔离?
这是一个最基础的并查集的应用,扫描每一个社团,只要两个学生出现在同一个社团,则将这两个集合合并起来,最后输出0号点所在集合的rank值集合(rank值记录这个集合中的元素个数并用一个flag值跟踪0号元素所在集合标号)即可。
这是并查集问题的第一种应用:集合合并,判断两点是不是在同一个集合,求某一个集合上的元素个数等。

#include<stdio.h>

#define MAX 
30000
int f[MAX];//这里的1001只是一个示意性的数字 代表初始状态下的分支数目
int r[MAX];
int flag;
//由于不知道应该将子树挂到那个集合上面去,故需要一个准则,这里的准则是将子树挂到
//r值大的集合上面去,初始状态下r数组的值均为一,代表每个分支下只有一个数字





int find(int n)
{
    
if(f[n]==n)
        
return n;
    
else
        f[n]
=find(f[n]);
    
return f[n];
}
//查找函数,并压缩路径


int Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    
if(a==b)
        
return 0;
    
else if(r[a]<=r[b])
    
{
        f[a]
=b;
        r[b]
+=r[a];
        
if(a==flag)
            flag
=b;
    }

    
else
    
{
        f[b]
=a;
        r[a]
+=r[b];
        
if(b==flag)
            flag
=a;
    }

    
return 1;
    
}
//合并函数,如果属于同一分支则返回0,成功合并返回1



int main()
{

    
int n,m;
    
int i,j;
    
int num;
    
int maxnum=0;

    
while(scanf("%d%d",&n,&m))
    
{
        flag
=0;
        maxnum
=0;
        
int temp1,temp2;

        
if(n==0&&m==0)
            
break;
        
for(i=0;i<n;i++)
        
{

            f[i]
=i;
            r[i]
=1;
        }

        
for(j=1;j<=m;j++)
        
{
            scanf(
"%d",&num);
            
for(i=0;i<num;i++)
            
{
                
if(i==0)
                    scanf(
"%d",&temp1);
                
else
                
{
                    scanf(
"%d",&temp2);
                    Union(temp1,temp2);
                }

            }

        }


        printf(
"%d\n",r[flag]);
        

    }

    
return 0;
}



POJ 2492 A Bug's Life
个人认为它是初级并查集问题的一个升级。同时这个题让我看到了食物链的影子。。。
题目的大意是给出n只bug和m次观察到的性行为,并以此为依据判断两只bugs是不是有同性恋行为(gay)。
比如3只bug
1 2有性行为
2 3有性行为
1 3有性行为
---->>>>>首先1,2是异性。
---->>>>>然后2,3是异性。
可以推出1,3是异性。
但是1,3有性行为,所以可以判断出有一定有同性恋。

剥离这个题目所赋予的外壳,我们抽出这个问题的本质:并查集!
其实,这里最重要的是去维护每一个点到集合顶点的偏移量。(注意:下面生造了一个词 所谓集合元素 比如说f[i]=i,那么i就是集合元素,集合偏移量就是集合元素的偏移量)

初始状态下,应该是
i号点挂在i号集合下面
我们考虑一般情况:假设合并的过程已经进行了一部分 ,这样每一个集合下面都有元素,且各自对于顶点的偏移量都算出来了;
现在在a集合中的元素x和b集合中的元素y进行合并。此时有两中情况改变偏移量;
1.首先是集合的合并,如果要将a,b集合合并,又要保证x,y数字的kind不相同,比如说把b集合挂到a集合下面去。
代表集合的那个元素,他的偏移量永远是0,所以b要改变偏移量,使得b里面的y在进行变换后要和x相异。
如果 kind[x]=0;kind[y]=0;那么y对应的那个代表集合的元素的偏移量必须变成1,因为只有这样才能使得合并后,x,y有不同的kind;
如果 kind[x]=0,kind[y]=1;y对应代表集合的元素偏移量是0,所以对应集合偏移量还是0;
类推   kind[x]=1,kind[y]=0,同上,0;
           kind[x]=1,kind[y]=1,y集合偏移量应该变为1;
综上 可以得到一个同或的关系。
用等式 kind[a]=(kind[x]+kind[y]+1)%2;恰好满足要求.
2.然后是压缩路径时候的偏移量改变
个人认为,这个主要是解决集合合并时候产生的“残余问题”,因为在合并集合的时候只是考虑了集合的偏移量,至于它下面的元素一概不管。一个压缩路径既分离了父子元素的偏移量,又使得子元素直接指向集合元素。

总而言之,并查集的操作就是不断地维护者各个集合中,每个元素身上对集合元素的偏移关系。从而确定他们是否具有同性恋。
在这个题中,假设是不存在同性恋的,所以只有找到矛盾才输出 有同性恋。
#include<iostream>
#include
<cstdio>
using namespace std;
#define MAX 2001

int f[MAX];
int kind[MAX];

int n,m;
int testcase;

void init()
{
    
int i;
    
for(i=1;i<=n;i++)
    

        f[i]
=i;
        kind[i]
=0;
    }

}


int Find(int n)
{
    
    
if(f[n]==n)
        
return n;
    
int t=Find(f[n]);
    kind[n]
=(kind[n]+kind[f[n]])%2;
    f[n]
=t;
    
return f[n];
}


int  Union(int x,int y)
{
    
    
int a=Find(x);
    
int b=Find(y);
    
if(a==b)
    
{
        
if(kind[x]==kind[y])
            
return 1;//1代表有同性恋情况
    }

    
else 
    
{
        f[a]
=b;
        kind[a]
=(kind[x]+kind[y]+1)%2;
    }

    
return 0;
}






int main()
{
    scanf(
"%d",&testcase);
    
int i,j;
    
int a,b;
    
int flag;
    
for(i=1;i<=testcase;i++)
    
{
        flag
=0;
        scanf(
"%d%d",&n,&m);
        init();
        
for(j=1;j<=m;j++)
        
{
            scanf(
"%d%d",&a,&b);
            
if(Union(a,b))
            
{
                flag
=1;
            }

        }

        
if(flag==1)
            printf(
"Scenario #%d:\nSuspicious bugs found!\n\n",i);
        
else 
            printf(
"Scenario #%d:\nNo suspicious bugs found!\n\n",i);


    }

    
return 0;
}



POJ 1182 食物链 
中文题,让你输出假话的个数。其实这道题是上一道题的扩展,如果把上一道题也想成是食物链的话,就是1吃2,2吃1.
而这里是三个动物,所以同样是维护一个偏移量,只不过多了一位罢了。
程序的过程实质上就是在维护并查集,判断是否是假话是在维护的过程中进行的,只能算是附属品吧。
#include<iostream>
using namespace std;
#define MAX 50005

int f[MAX];
int kind[MAX];

int n,m;

void init()
{
    
int i;
    
for(i=1;i<=n;i++)
    

        f[i]
=i;
        kind[i]
=0;
    }

}


int Find(int n)
{
    
    
if(f[n]==n)
        
return n;
    
int t=Find(f[n]);
    kind[n]
=(kind[n]+kind[f[n]])%3;
    f[n]
=t;
    
return f[n];
}

bool  Union(int x,int y,int c)
{
    
if(x>n||y>n)
        
return 1;
    
int a=Find(x);
    
int b=Find(y);
    
if(c==1)
    
{
        
if(a==b)
        
{

            
if(kind[x]!=kind[y])
                
return true;
        }

        
else if(a!=b)
        
{

            f[b]
=a;
            kind[b]
=(kind[x]-kind[y]+3)%3;
        }

    }

    
else
    
{
        
if(x==y)
            
return true;
        
if(a==b)
        
{
            
if((kind[x]+1)%3!=kind[y])
                
return true;
        }

        
else if(a!=b)
        
{
            f[b]
=a;
            kind[b]
=(kind[x]-kind[y]+4)%3;
        }


    }

    
return false;
}


int main()
{
    
int i,j;
    
int a,b,c;
    
int sum=0;
    scanf(
"%d%d",&n,&m);
    init();
    
for(i=1;i<=m;i++)
    
{
        scanf(
"%d%d%d",&c,&a,&b);
        
if(Union(a,b,c))
            sum
++;
    }

    printf(
"%d\n",sum);
    
return 0;
}



 这里将两个集合并起来并将所挂集合偏移量指向:
kind[b]=(kind[x]-kind[y]+4)%3;
想想上一题是不是也很类似呢
其实上一题的公式也可以改成
kind[b]=(kind[x]-kind[y]+3)%2;
不管是几个动物循环,都能得到类似的结论,所以以后碰到4,5,6,7。。。个动物的食物链,你应该也会做了吧?^_^

POJ 1988 Cube Stacking
这道题更有意思了,说它开辟了并查集问题的新局面并不为过;上面2道题,研究的主要是到集合元素的偏移量,而这道题要求的是一个“逻辑上”到达集合元素的距离!集合合并的时候同样只修改被挂集合元素的距离值,残余部分留给压缩路径来处理.
如果理解了上面的问题,这个问题就很好理解了。
#include<iostream>
#include
<algorithm>
#include
<cmath>
using namespace std;
#define MAX 30000



int f[MAX+1];
int r[MAX+1];
int above[MAX+1];

void init()
{

    
int i;
    
for(i=1;i<=MAX;i++)
    
{
        above[i]
=0;
        f[i]
=i;
        r[i]
=1;
    }

}


int realfather;
int find(int n)
{
    
int t;
    
if(f[n]==n)
    
{
        realfather
=n;
        
return n;
    }

    
else
    
{
        t
=find(f[n]);
        
if(f[n]!=realfather)
            above[n]
+=(above[f[n]]);
        f[n]
=t;

    }

    
return f[n];
}
//查找函数,并压缩路径


void Union(int x,int y)
{
    
int a=find(x);
    
int b=find(y);
    f[b]
=a;
    above[b]
+=r[a];
    r[a]
+=r[b];
    
    
}
//合并函数,如果属于同一分支则返回0,成功合并返回1

int main()
{
    
int p;
    
int i;
    init();
    
char order;
    
int a,b;
    scanf(
"%d",&p);
    
for(i=1;i<=p;i++)
    
{
        cin.ignore();
        scanf(
"%c",&order);
        
if(order=='M')
        
{

            scanf(
"%d%d",&a,&b);
            Union(a,b);
        }

        
else if(order=='C')
        
{
            scanf(
"%d",&a);
            printf(
"%d\n",r[find(a)]-above[a]-1);
        }


    }

    
return 0;
}

银河英雄传说 NOI 2002
说道并查集,还有一道非常经典的题目 还有那个“著名”的杨威利元帅,呵呵。这题附上原题,有了上面的讲解,相信你能很快找到解法^_^

银河英雄传说


【问题描述】

公元五八○一年,地球居民迁移至金牛座α第二行星,在那里发表银河联邦创立宣言,同年改元为宇宙历元年,并开始向银河系深处拓展。

宇宙历七九九年,银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征,气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜多,难免恣生骄气。在这次决战中,他将巴米利恩星域战场划分成30000列,每列依次编号为1, 2, …, 30000。之后,他把自己的战舰也依次编号为1, 2, …, 30000,让第i号战舰处于第i(i = 1, 2, …, 30000),形成“一字长蛇阵”,诱敌深入。这是初始阵形。当进犯之敌到达时,杨威利会多次发布合并指令,将大部分战舰集中在某几列上,实施密集攻击。合并指令为M i j,含义为让第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而,老谋深算的莱因哈特早已在战略上取得了主动。在交战中,他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时,莱因哈特为了及时了解当前杨威利的战舰分布情况,也会发出一些询问指令:C i j。该指令意思是,询问电脑,杨威利的第i号战舰与第j号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员,你被要求编写程序分析杨威利的指令,以及回答莱因哈特的询问。

最终的决战已经展开,银河的历史又翻过了一页……


【输入文件】

输入文件galaxy.in的第一行有一个整数T1<=T<=500,000),表示总共有T条指令。

以下有T行,每行有一条指令。指令有两种格式:

  1. M i j ij是两个整数(1<=i , j<=30000),表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令,并且保证第i号战舰与第j号战舰不在同一列。

  2. C i j ij是两个整数(1<=i , j<=30000),表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。


【输出文件】

输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理:

如果是杨威利发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

 如果是莱因哈特发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上,则输出-1


【样例输入】

4

M 2 3

C 1 2

M 2 4

C 4 2


【样例输出】

-1

1


【样例说明】

战舰位置图:表格中阿拉伯数字表示战舰编号


第一列

第二列

第三列

第四列

……

初始时

1

2

3

4

……

M 2 3

1


3

2

4

……

C 1 2

1号战舰与2号战舰不在同一列,因此输出-1

M 2 4

1



4

3

2

……

C 4 2

4号战舰与2号战舰之间仅布置了一艘战舰,编号为3,输出1

 

不知道并查集问题还有没有什么别的变种呢?除了维护偏移量和到顶点的距离,还有没有可能是别的情况呢?比如说。。。。。。如果你有更好的想法,欢迎和我交流。


文章由abilitytao原创
转载请注明出处:http://www.cppblog.com/abilitytao/archive/2009/10/18/98899.html

posted on 2009-10-18 21:31 abilitytao 阅读(3124) 评论(5)  编辑 收藏 引用

评论

# re: 并查集学习小节(POJ版) 2009-11-12 08:54 ljf

cube stacking 那个find中没必要用那个realfather吧?
因为above[realfather] = 0
加不加那个判断都无所谓,是不是?  回复  更多评论   

# re: 并查集学习小节(POJ版) 2010-05-14 16:43 lqq

第一题,那个压缩路径的算法好像少了一点东西  回复  更多评论   

# re: 并查集学习小节(POJ版) 2010-07-18 12:07 简单就好

Union函数不用返回值,可定义为void型  回复  更多评论   

# re: 并查集学习小节(POJ版) 2010-07-18 22:04 abilitytao

@简单就好
返回值为1代表合并成功,返回值为0代表合并不成功。  回复  更多评论   

# re: 并查集学习小节(POJ版) 2015-07-19 09:01 谢谢

xiexie  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理