首页 > 代码库 > HDU1232 畅通工程

HDU1232 畅通工程

2024-07-13 19:55:17   216人阅读

题目 大意：

在已给定的城市数量，和城市间连接的轨道，问至少还需建多少轨道，才能保证整个城市能全部连通。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1232

 

这题目是在无向条件下进行简单的并查集操作，最后求出来有多少个连通分量count，则修建的路即为count-1

 

代码如下：

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5  6 #define MAXN 1010 7 int fa[1010]; 8  9 int getHead(int x)10 {11     while(x!=fa[x]) x=fa[x];12     return x;13 }14 15 void Union(int x,int y)16 {17     int fa_x=getHead(x);18     int fa_y=getHead(y);19     fa[fa_x]=fa_y;20 }21 22 int main()23 {24     int N,M,a,b;25     while(scanf("%d",&N)&&N!=0){26         for(int i=1;i<=N;i++) fa[i]=i;27         scanf("%d",&M);28         for(int i=0;i<M;i++){29             scanf("%d%d",&a,&b);30             Union(a,b);31         }32 33         int count=0;34         for(int i=1;i<=N;i++)35             if(fa[i]==i) count++;36 37         printf("%d\n",count-1);38     }39     return 0;40 }


联系
我们