链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232
这道题目,是一道很清楚的并查集模板题。
首先给你两个数据,表示城镇数量N和道路数量M
接下来会告诉你哪几个城市已经通路了
剩下的就是你要算出,至少要需要多少条路。
http://download.csdn.net/detail/l_oser/4513396。
AC代码如下:
#include<iostream> #include<stdio.h> using namespace std; int parent[1005]; int n,m; int sum; int Find(int x) //查找父亲节点 { if(parent[x]==x) return x; return parent[x]=Find(parent[x]); } void Union(int a,int b)//合并 { if(a!=b) { parent[a]=b; sum++; } } int main() { while(scanf("%d %d",&n,&m)) { if(n==0) break; int i; for(i=1;i<=n;i++) parent[i]=i; //初始化父亲节点 sum=0; int v,u; for(i=0;i<m;i++) { scanf("%d %d",&v,&u); Union(Find(v),Find(u)); //通过判断两个集合的父亲节点是否相同,然后考虑是否合并 } printf("%d\n",n-1-sum); //总道路数= n-1,减去已经修建好的,便是还要修建的。 } return 0; }