追击题解

admin 2025-11-02 19:04:29

题解

对于两个点集 ,如果 ,那么两个点集中的点一定在一个连通块内,直接用dsu就行。

代码

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

struct DSU
{
    vector<int> dsu;
    DSU(int n)
    {
        dsu.assign(n, 0);
        iota(dsu.begin(), dsu.end(), 0);
    }
    int find(int x)
    {
        return dsu[x] == x ? x : dsu[x] = find(dsu[x]);
    }
    void add(int x, int y)
    {
        int rx = find(x), ry = find(y);
        if (rx != ry)
        {
            dsu[ry] = rx;
        }
    }
};
void solve()
{
    int n, m;
    cin >> n >> m;
    DSU dsu(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        if (!x || !y)
        {
            int tmp;
            for (int i = 1; i <= x + y; i++)
            {
                cin >> tmp;
            }
            continue;
        }
        int a;
        cin >> a;
        for (int i = 1; i < x + y; i++)
        {
            int b;
            cin >> b;
            dsu.add(a, b);
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (dsu.find(u) == dsu.find(v))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}