#include <bits/stdc++.h>
using namespace std;
int n, m, q; // 人数、关系数量、询问数量
int col[21234];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// 染上初始颜色
for (int i = 1; i <= n; i++)
col[i] = i;
// 处理 m 组关系
while (m--)
{
int u, v;
cin >> u >> v;
// u所在的家族与v所在的家族合并
// 把所有颜色与 v 一样的人，都染成 u 的颜色
int vCol = col[v];
for (int i = 1; i <= n; i++)
if (col[i] == vCol)
col[i] = col[u];
}
// 处理q组询问
cin >> q;
while (q--)
{
int u, v;
cin >> u >> v;
if (col[u] == col[v])
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, m, q; // 人数、关系数量、询问数量
int fa[21234]; // fa[i]: 记录 i 的父节点
// 返回x的祖宗节点
int findFa(int x)
{
if (x == fa[x])
return x;
return findFa(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// 初始每个人自己是自己的祖宗
for (int i = 1; i <= n; i++)
fa[i] = i;
// 处理 m 组关系
while (m--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
fa[faV] = faU;
}
// 处理q组询问
cin >> q;
while (q--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
if (faU == faV)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
根据两个集合的大小来建立连接关系
#include <bits/stdc++.h>
using namespace std;
int n, m, q; // 人数、关系数量、询问数量
int fa[21234]; // fa[i]: 记录 i 的父节点
int cnt[21234]; // cnt[i]: 记录家族人数（只有是祖宗节点时才有效）
// 返回x的祖宗节点
int findFa(int x)
{
if (x == fa[x])
return x;
return findFa(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// 初始每个人自己是自己的祖宗
for (int i = 1; i <= n; i++)
fa[i] = i, cnt[i] = 1;
// 处理 m 组关系
while (m--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
if (faU != faV)
{
if (cnt[faV] < cnt[faU])
{
fa[faV] = faU;
cnt[faU] += cnt[faV];
}
else
{
fa[faU] = faV;
cnt[faV] += cnt[faU];
}
}
}
// 处理q组询问
cin >> q;
while (q--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
if (faU == faV)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
找到了祖宗节点后就直接连上去
#include <bits/stdc++.h>
using namespace std;
int n, m, q; // 人数、关系数量、询问数量
int fa[21234]; // fa[i]: 记录 i 的父节点
// 返回x的祖宗节点
int findFa(int x)
{
if (x == fa[x])
return x;
// return fa[x] = findFa(fa[x]);
fa[x] = findFa(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// 初始每个人自己是自己的祖宗
for (int i = 1; i <= n; i++)
fa[i] = i;
// 处理 m 组关系
while (m--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
fa[faV] = faU;
}
// 处理q组询问
cin >> q;
while (q--)
{
int u, v;
cin >> u >> v;
// 找到两个人的祖宗节点
int faU = findFa(u);
int faV = findFa(v);
if (faU == faV)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}