最少好要修多少条路太能使全部城镇连通。只要用并查集算可以连通的城市的组数，修的路就是组数减1
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define C getchar() 4 template <typename T> 5 inline void read(T &s){ 6 T t=1; char k=C; s=0; 7 for (;k<'0'||k>'9';k=C) if (k=='-') t=-1;//判断该数正负 8 for (;k>='0'&&k<='9';k=C) s=(s<<1)+(s<<3)+(k^48);//<<1加上<<3就相当于*10，但是位运算的速度较快，^48也相当于-‘0’，同理，较快。 9 s*=t; 10 } 11 int f[10001]={0},n,m; 12 void init() 13 { 14 for(int i=1;i<=n;i++) 15 { 16 f[i]=i; 17 } 18 } 19 int getf(int v) 20 { 21 if(f[v]==v)return v; 22 else 23 { 24 f[v]=getf(f[v]); 25 return f[v]; 26 } 27 } 28 void merge(int v,int u) 29 { 30 int t1,t2; 31 t1=getf(v); 32 t2=getf(u); 33 if(t1!=t2) 34 { 35 f[t2]=t1; 36 37 } 38 return; 39 } 40 int main() 41 { 42 while(~scanf("%d",&n),n) 43 { 44 init(); 45 scanf("%d",&m); 46 for(int i=0;i<m;i++) 47 { 48 int x,y; 49 scanf("%d %d",&x,&y); 50 merge(x,y); 51 } 52 int ans=0; 53 for(int i=1;i<=n;i++) 54 { 55 if(getf(i)==i)ans++; 56 } 57 printf("%d ",ans-1); 58 } 59 return 0; 60 }