给出m个城镇,n条路,问还需修几条路才能连通所有城镇。
基本并查集问题
#include<iostream>
using namespace std;
#include<memory.h>
int city[1001];
int find(int pos)
{
if(city[pos]==-1)
return pos;
return city[pos]=find(city[pos]);
}
int merge(int a,int b)
{
int roota=find(a);
int rootb=find(b);
if(roota==rootb)
return 0;
city[roota]=rootb;
return 1;
}
int main()
{
int n,m;
int s,e;
int count;
while(1)
{
cin>>n;
memset(city,-1,sizeof(city));
if(n==0)
break;
cin>>m;
while(m--)
{
cin>>s;
cin>>e;
merge(s,e);
}
count = 0;
for(int i=1;i<=n;i++)
{
if(city[i]==-1)
count++;
}
cout<<count-1<<endl;
}
}
分享到:
相关推荐
软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程复试资料软件工程...
机械设计考研复试真题参考资料,最新2022届考研复试可用。上海工程技术大学车辆工程复试参考资料
东北大学 计算机复试 软件工程 ppt
软件工程复试资料。。软件工程复试资料。可以参考一下,
哈工程考研数据库复试资料,分享给大家。
北京理工大学光学工程考研复试真题02-05,照片,可以针对本真题对考研复试有针对性的准备,北理工光学光学工程,可以看看自己学的怎么样哦
软件工程考研 软件工程复试 软件工程 软工复习资料
哈工程复试计算机所用的材料,分享出来,供给大家学习使用,希望大家也能成功上岸,加油。 哈工程复试计算机所用的材料,分享出来,供给大家学习使用,希望大家也能成功上岸,加油。 哈工程复试计算机所用的材料,...
中石油(华东)考研控制工程专业复试科目过程控制工程的复习资料
南京信息工程大学软件工程复试思维导图
南理工数据库与软件工程复试资料 上课课件及试卷
哈工程本科上课所用的课件 可供考研的同学参考
郑州大学计算机专业历年复试专业课真题,408专业,944专业 软件工程专业复试真题 郑州大学英语复试题目
东北大学复试 软件工程 20100510-软件工程
软件工程简答题(东南复试)软件工程简答题(东南复试)软件工程简答题(东南复试)软件工程简答题(东南复试)软件工程简答题(东南复试)
北邮计算机复试软件工程试题(A)附答案
复试科目《网络工程》参考资料,大家可以下载看下,加油! 复试科目《网络工程》参考资料,大家可以下载看下,加油!
西北大学软件工程考研复试资料,包括西北大学软件工程专业上机题目及复试笔试数据库,计算机网络及面试指导
传媒大学 复试笔试 软件工程2004——2016
该资源为东南大学桥梁工程历年考研复试真题,资源高清无水印哦! 该资源为东南大学桥梁工程历年考研复试真题,资源高清无水印哦!