树的应用 - 并查集
标签: 数据结构
学习人数: 13.0k

先来看一个题目作为例子

http://www.noobdream.com/DreamJudge/Issue/page/1319/

首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点,让你判断它们是否连通,或者问你整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。像畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。

如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;如果是3个连通分支,则只要再修两条路……
以下面这组数据输入数据来说明
4 2

1 3

4 3
第一行告诉你,一共有4个点,2条路。下面两行告诉你,1、3之间有条路,4、3之间有条路。那么整幅图就被分成了1-3-4和2两部分。只要再加一条路,把2和其他任意一个点连起来,畅通工程就实现了,那么这个这组数据的输出结果就是1。好了,现在编程实现这个功能吧,城镇有几百个,路有不知道多少条,而且可能有回路。 这可如何是好?

题目的详细讲解:http://www.noobdream.com/Major/article/138/

 

下面举个例子让大家更容易懂并查集的原理

 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的帮派,通过两两之间的朋友关系串联起来。而不在同一个帮派的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物。这样,每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样,想打一架得先问个几十年,饿都饿死了,受不了。这样一来,队长面子上也挂不住了,不仅效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否是一个帮派的,至于他们是如何通过朋友关系相关联的,以及每个圈子内部的结构是怎样的,甚至队长是谁,都不重要了。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

下面我们来看并查集的实现。 int fa[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),fa[1...

登录查看完整内容


课后作业

学习并掌握并查集

http://www.noobdream.com/Major/article/138/


登录后开始许愿

暂无评论,来抢沙发