hdu1213 How Many Tables
基础并查集。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int par[maxn],n,m;void init(){for(int i=1;i<=n;i++)par[i]=i;
}int fi(int x){if(par[x]!=x) return par[x]=fi(par[x]);return par[x];
}void join(int x,int y){int fx=fi(x),fy=fi(y);if(fx!=fy){par[fy]=fx;}
}int main(){int t;scanf("%d",&t);while(t--){//printf("t=%d\n",t);scanf("%d%d",&n,&m);init();int a,b;while(m--){scanf("%d%d",&a,&b);join(a,b);}int cnt=0;for(int i=1;i<=n;i++){if(par[i]==i) cnt++;}printf("%d\n",cnt);//if(t!=0) printf("\n");}return 0;
}