HDU 1232 畅通工程

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<set>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cmath>
 7 using namespace std;
 8 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 9 #define FORD(i,j,k) for(int i=j;i>=k;i--)
10 #define LL long long
11 #define maxn 1010
12 int T,ans,m,n,x,y;
13 int a[maxn],fa[maxn];
14 int father(int x)
15 {
16     if(fa[x]==x) return x;
17     else return fa[x]=father(fa[x]);
18 }
19 void setunion(int x,int y)
20 {
21     if(father(x)!=father(y))
22     fa[father(x)]=father(y);
23 }
24 // setsearch(x)  return fa[x];
25 int main()
26 {
27 for(cin>>n;n!=0;cin>>n)
28 {
29     //init
30     cin>>m;
31     FOR(i,1,n)
32     fa[i]=i;
33     FOR(i,1,m)
34     {cin>>x>>y;setunion(x,y);}
35     
36     ans=0;
37     //check
38     FOR(i,1,n-1)
39     if(father(i)!=father(i+1))
40     {setunion(i,i+1);    ans++;}
41     
42     //prints
43     cout<<ans<<endl;
44     
45     //clear
46     FOR(i,1,n)
47     {a[i]=0; fa[i]=0;}
48 }
49 return 0;
50 }