HDU 1213 How Many Tables

题目链接：HDU 1213 How Many Tables

思路

       经典并查集，将互相认识的人全部放在一个集合内，然后计算有几个集合就有几个桌子。

代码

#include <iostream>
using namespace std;
#define ll long long
const int N = 1e3 + 10;

int fa[N];

void init(int n) {
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
}

int find(int x) {
  if (x == fa[x])
    return x;
  else
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
  fa[find(x)] = find(y);
}

void solve() {
  int n, m;
  cin >> n >> m;

  init(n + 10);

  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    merge(a, b);
  }

  int num = 0;
  for (int i = 1; i <= n; i++) {
    if (fa[i] == i) {
      num++;
    }
  }
  cout << num << endl;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}