畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21505 Accepted Submission(s): 11156
Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
注意:两个城市之间可以有多条道路相通,也就是说
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 998Huge input, scanf is recommended.HintHint
Source
Recommend
JGShining
解题思路:本题用并查集解答,所有连通的城镇以相同根节点的数组存储,所有连通的城镇有同一根节点,最后统计不同根节点种数即可得到相互不连通的城镇集合(n群),即可求的需建立的道路数(n-1)。
#include<stdio.h> #include<string.h> int town[1002]; //存储城镇连通情况,并查集根节点 int n,m; int find(int x) //查找根节点 { while(x != town[x]) //该节点非根节点,寻找根节点 x = town[x]; //若该节点为根节点,直接返回该节点值 return x; } void union1(int a,int b) //将a,b两个集合连接合并为一个集合(可能本来为同一集合) { int a_f=find(a),b_f=find(b); //分别查找两个集合的根节点 if(a_f!=b_f) //若根节点不同,即为不同集合,则合并两个集合 town[b_f]=a_f; } int main() { int i,j,k; int a,b; int sum[1002]; //记录每个城镇连通集合的根节点 while(scanf("%d",&n)&&n) { memset(town,0,sizeof(town[0])*(n+1)); //存储结构初始化 memset(sum,0,sizeof(sum[0])*(n+1)); for(i=1;i<=n;i++) //未知连通情况事,每个节点为一个集合,其根节点为其本身 town[i]=i; scanf("%d",&m); while(m--) { scanf("%d%d",&a,&b); union1(a,b); //得知a,b连通后,将a,b两个集合合并 } for(i=1; i<=n; i++) //统一每个集合的根节点,使同一个集合根节点相同 town[i] = find(town[i]); for(i=1;i<=n;i++) //统计城镇节点作为根节点的情况(遍历城镇连通情况表) sum[town[i]]=1; int x=0; for(i=1;i<=n;i++) //统计根节点个数(不连通集合个数) x+=sum[i]; printf("%d\n",x-1); } return 0; }