I. Invoking the Magic

原题链接

题意

题目其实比较好理解，就是给定n对袜子（袜子保证有且只有两只，也就是保证数据一定合理）。我们可以把一些袜子放到洗衣机里面，但要保证这些袜子可以两两配对。让我们去求一次性最多可以弄多少双这样的袜子。

题解

如果要两两配对我们就可以通过画图的方式将轨迹连成一个圈，所以我们可以用并查集来进行，因为题目的条件我们最后就看最后有几组，然后在这几个组里面求一个最大的值（别忘了除以二，因为问的几双袜子）

数据比较大可以用哈希表来求，但是map速度有点慢，要用unordered_map,还有就是要用解除同步的cin和cout(scanf 和 printf 会超时）虽然我也不知道怎么回事

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
unordered_map<LL, LL> q, p;
LL a[N], b[N];

LL find(LL x)
{
    if (q[x] != x)
        q[x] = find(q[x]);
    
    return q[x];
}

void solve()
{
    q.clear(), p.clear();

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];

        q[a[i]] = a[i];
        q[b[i]] = b[i];
    }

    for (int i = 0; i < n; i ++)
    {
        if (find(a[i]) != find(b[i]))
            q[find(a[i])] = find(b[i]);
    }

    LL res = 0;
    for (int i = 0; i < n; i ++)
    {
        p[find(a[i])] ++;
        p[find(b[i])] ++;

        res = max(res, p[find(a[i])]);
        res = max(res, p[find(b[i])]);
    }

    cout << res / 2 << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;

    while (T --)
    {
        solve();
    }
    return 0;
}