题解
对于两个点集 和 ,如果 ,那么两个点集中的点一定在一个连通块内,直接用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;
}