并查集经典畅通工程-白红宇

并查集经典畅通工程

阅读量：5051 次

发布时间：2019-06-12

本文共 1221 字，大约阅读时间需要 4 分钟。

题目描述

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

输入

测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N(N<1000)和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。

注意:两个城市之间可以有多条道路相通,也就是说：

3 3

1 2

2 1

这种输入也是合法的

当N为0时，输入结束，该用例不被处理。

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int maxn = 1005;int fa[maxn];int findfa(int x) //并查集的两种操作 1.找father （寻找根）{ int rtfa = x; while(rtfa!=fa[rtfa]) rtfa = fa[rtfa]; int i=x,j; //路径压缩 将途中所有的点的father从上一级改到根 while(fa[i]!=rtfa) { j = fa[i]; fa[i] =rtfa; i = j; } return rtfa;}void join(int x,int y) //2.合并fa （将y加入到x的集合中）{ int fx = findfa(x); int fy = findfa(y); if(fx!=fy) fa[fx] =fy;}int main(){ int n,m; while(cin>>n&&n!=0) { cin>>m; for(int i=1;i<=n;i++) //初始化 开始不连接时每个都是单独的一个集合 各自的father都是自己 { fa[i] = i; } for(int i=0;i
             
              >x>>y; join(x,y); } bool vis[maxn] = { false}; for(int i=1;i<=n;i++) { vis[findfa(i)] = true; //找共有几个根节点 } int ans = 0; for(int i=1;i<=n;i++) { if(vis[i]) ans++; } cout<
              
               <

转载于:https://www.cnblogs.com/hao-tian/p/9456094.html

你可能感兴趣的文章