时间复杂度相关内容

染色

#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;
}