学步园

并查集 入门题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1213

#include <iostream>
using namespace std;

int father[1001];
int rank[1001];

void Make_Set(const int n)
{
 for (int i = 1; i <= n; i++) {
  father[i] = i;
  rank[i] = 0;
 }
}
int Find_Set(const int x) {
 if (x != father[x])
  father[x] = Find_Set(father[x]);
 return father[x];
}
void Union(int x, int y) {
 x = Find_Set(x);
 y = Find_Set(y);
 if (x == y) return ;
 if (rank[x] < rank[y]) father[x] = y;
 else if (rank[y] < rank[x]) father[y] = x;
 else {
  rank[x] ++; father[y] = x;
 }
}

int main()
{
 int t, a, b, n, m;
 int i, count;
 scanf("%d", &t);
 while (t--) {
  scanf("%d %d", &n, &m);
  Make_Set(n);
  while (m--) {
   scanf("%d %d", &a, &b);
   Union(a, b);
  }
  count = 0;
  for (i = 1; i <= n; i++)
   if (i == father[i])
    count ++;
  cout << count << endl;
 }
 return 0;
}