题解

读题，知道要求的是并查集数量，一道板子

# include <bits/stdc++.h>
typedef unsigned long long ull;

#pragma GCC optimize(3)
#define get getchar_unlocked()
#define phc push_back
#define vec vector
#define endl '\n'
#define beg(x) x.begin(),x.end()
#define mkp make_pair
#define lowb lower_bound
#define uppb upper_bound
#define px(a) sort(beg(a));
#define i3 * 2863311531LL >> 33
#define itn int

using  namespace  std ;
const int n = 1e3 + 3;
const int wqd = INT_MAX;
int readOneInt() {
    int x = 0, f = 1;
    char c = get;
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = get;}
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = get;
    return x * f;
}
int fat[n], siz[n]; // 祖先，祖先大小
// 路径压缩
int fin(int x) {
    return (fat[x] == x? x: fat[x] = fin(fat[x]));
}
// 启发式合并
void merg(int a, int b) {
    a = fin(a), b = fin(b); // 找祖先
    if (siz[a] < siz[b]) swap(a, b); // 小于则交换
    siz[a] += siz[b], fat[b] = a; // 把 b 挂到 a 上
}
void SuckMyBanana() {
    int N = readOneInt(), m = readOneInt(), ct = 0;
    for (int i = 1; i <= N; ++i) siz[i] = 1, fat[i] = i;
    while (m--) merg(readOneInt(), readOneInt());
    // 求并查集数量等于求祖先数量
    for (int i = 1; i <= N; ++i) if (fat[i] == i) ct++;
    cout << ct << endl;
}
int  main ( )
{
    int total_textcases = readOneInt();
    while (total_textcases -- || 0) SuckMyBanana(); 
    return  1 + 1 - 4 + 5 + 1 - 4;
}