纯染色

$O(nm+q)$，72 分

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int col[20000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        col[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        int colU = col[u];
        for (int j = 1; j <= n; j++)
            if (col[j] == colU)
                col[j] = col[v];
    }
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (col[u] == col[v])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

染色优化

颜色一样的就不染，每次染色都会减少一个颜色，最多染 $n-1$ 次，$O(n^2+q)$，$100$ 分

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int col[20000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        col[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        if (col[u] == col[v])
            continue;
        int colU = col[u];
        for (int j = 1; j <= n; j++)
            if (col[j] == colU)
                col[j] = col[v];
    }
    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;
}