鱼C论坛

 找回密码
 立即注册
查看: 47|回复: 1

[学习笔记] 023:畅通工程 - 并查集

[复制链接]
最佳答案
17 
发表于 2018-2-13 10:48:59 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Messj 于 2018-6-8 23:39 编辑

Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?


Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。


Output
对每个测试用例,在1行里输出最少还需要建设的道路数目。


Sample Input
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0


Sample Output
1
0
2
998

本帖被以下淘专辑推荐:

最佳答案
17 
 楼主| 发表于 2018-2-13 10:50:23 | 显示全部楼层
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

  1. #include<cstdio>
  2. #define N 1000

  3. using namespace std;

  4. int tr[N];
  5. int findroot(int x)
  6. {
  7.         if(tr[x]==-1)
  8.                 return x;
  9.         else
  10.         {
  11.                 int tmp=findroot(tr[x]);
  12.                 tr[x]=tmp;
  13.                 return tmp;
  14.         }
  15. }

  16. int main()
  17. {
  18.         int n,m;
  19.         while(scanf("%d",&n)!=EOF&&n!=0)
  20.         {
  21.                 scanf("%d",&m);
  22.                 for(int i=1;i<=n;i++)
  23.                         tr[i]=-1;
  24.                 while(m--)
  25.                 {
  26.                         int a,b;
  27.                         scanf("%d%d",&a,&b);
  28.                         a=findroot(a);
  29.                         b=findroot(b);
  30.                         if(a!=b)
  31.                                 tr[a]=b;
  32.                 }
  33.                 int ans=0;
  34.                 for(int i=0;i<=n;i++)
  35.                         if(tr[i]==-1)
  36.                                 ans++;
  37.                 printf("%d\n",ans-1);
  38.         }
  39.         return 0;
  40. }
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-8-15 09:45

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表