题目描述:
题解思路:很明显总道路数应该是村子数-1 只需要判断有多少条重复的道路即可 结果即为(n-1-(m-重复数))
代码:
#include<iostream> #include<cstdio> using namespace std; const int maxn=1000+10; int par[maxn]; int rank1[maxn]; int n,m; int tol[maxn]; //统计祖先结点为i的节点数为tol[i] void init(){ for(int i=1;i<=n;i++){ par[i]=i; rank1[i]=0; tol[i]=0; } } int find(int x){ if(par[x]==x) return x; else return par[x]=find(par[x]); } void unite(int x,int y){ x=find(x); y=find(y); if(x==y) return; if(par[x]<par[y]){ par[x]=y; }else{ par[y]=x; if(par[x]==par[y]){ rank1[x]++; } } } bool same(int x,int y){ return find(x)==find(y); } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0) return 0; init(); //每组数据都初始化 int sum=0; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; //在道路连接前先判断两个点是否已经连接过 if(same(a,b)) sum++; else unite(a,b); //未连接过则进行进行道路连接 } cout<<n-1-(m-sum)<<endl; //目前最少需要连接数 } return 0; }