首页 > 代码库 > 浙大 2005 畅通工程
浙大 2005 畅通工程
题目:
给出城镇数目N ( < 1000 )和道路数目M;以及每条道路直接连通的两个城镇的编号(1到N编号)。输出最少还需要建设的道路数目,使任何两个城镇间都直接或间接连通。
思路:
并查集。通过并查集判断真正起到链接作用,且不重复的路的数量,再求还需要建的路的数量。
代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <cstring> 4 using namespace std; 5 6 int roadNum; //符合的路的数量 7 //并查集 8 int Tree[1005]; 9 int find(int x){ //查根并压缩树 10 int ret,t; 11 int temp=x; 12 while(Tree[x]!=-1){ 13 x=Tree[x]; 14 } 15 ret=x; 16 x=temp; 17 while(Tree[x]!=-1){ 18 t=Tree[x]; 19 Tree[x]=ret; 20 x=t; 21 } 22 return ret; 23 } 24 void connect(int a,int b){ //合并两棵树 25 int ret1=find(a); 26 int ret2=find(b); 27 if(ret1==ret2) //自己通往自己的和同根的不处理 28 return ; 29 else{ 30 Tree[ret2]=ret1; 31 roadNum++; 32 return ; 33 } 34 } 35 36 //主函数 37 int main(){ 38 int N,M,i; 39 int m1,m2; 40 while(scanf("%d",&N)!=EOF && N){ //输入N 41 scanf("%d",&M); //输入M 42 memset(Tree,-1,1005*sizeof(int)); //初始化变量 43 roadNum=0; 44 for(i=0;i<M;i++){ //循环输入路 45 scanf("%d %d",&m1,&m2); 46 connect(m1,m2); //连接两点的根 47 } 48 printf("%d\n",N-1-roadNum); //还要再建的路 49 } 50 return 0; 51 }
浙大 2005 畅通工程
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。