hdu1213(并查集).MD

日期 2022 / 03 / 24

题目

Problem Descrption

Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

2

5 3

1 2

2 3

4 5

5 1 2 5

Sample Output

2

4

解题思路

这是一个基本的并查集的题目，题意是在聚会上，相互认识或者有共同朋友的人坐同一桌，给出t组数据，n表示总共有几个人，m表示有多少个认识关系 需要求现场需要布置多少张桌子， 我的思路是如果A->B表示A B两人相互认识，那么就应该把他们放进同一个集合里面，这也是并查集的思想，也类似一种建树的步骤，最终需要确定有多少个 根节点，即需要摆多少张桌子.

代码演示

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e3 + 10;
using namespace std;
int s[maxn];

void init() {
  for (int i = 1; i <= maxn; i++) {
    s[i] = i;	//初始化
  } 
}

int find_set(int i) {
  return s[i] == i ? i : find_set(s[i]); //寻找出根节点
}

void union_set(int x, int y) {
  x = find_set(x);
  y = find_set(y);
  if (x != y) {
    s[x] =  s[y];	 //合并节点
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t, x, y, n, m, cnt;
  cin >> t;
  while (t--) {
    init();
    cnt = 0;
    cin >> n >> m;	
    for (int i = 0; i < m; i++) {
      cin >> x >> y;
      union_set(x, y);
    }
    for (int i = 1; i <= n; i++) {
      if (s[i] == i) {
        cnt++;	
      }
    }
    cout << cnt << endl;
  }
  return 0;
}