HDU 1213 How Many Tables

Portal：http://acm.hdu.edu.cn/showproblem.php?pid=1213

模板题~开心

第一次写并查集

WA一次，PE一次才AC TAT

 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 cin>>T;
28 FOR(i,1,T)
29 {
30     //init
31     cin>>n>>m;
32     FOR(i,1,n)
33     fa[i]=i;
34     FOR(i,1,m)
35     {cin>>x>>y;setunion(x,y);}
36     
37     ans=1;
38     //check
39     FOR(i,1,n-1)
40     if(father(i)!=father(i+1))
41     {setunion(i,i+1);    ans++;}
42     
43     //print
44     cout<<ans<<endl;
45     
46     //clear
47     FOR(i,1,n)
48     {a[i]=0; fa[i]=0;}
49 }
50 return 0;
51 }

破破烂烂的AC代码

不过话说既然并查集是不相交动态集合的数据结构，那岂不是可以在无向图里乱搞？233