并查集

目标

  • 将两个集合合并
  • 查询两个元素是否在同一集合内

构造

每个集合用一棵树表示,用根节点的编号表示整个集合的编号,开一个数组 \(p[x]\) ,表示编号为 \(x\) 的元素的父节点编号

  • \(p[x] = = x, x\) 为树根。
  • \(x\) 的集合编号:while(p[x] != x) x = p[x]
  • 合并两个元素所在集合,设 \(px,py\) 表示 \(x,y\) 的集合编号,p[px]=py

路径压缩

这样的确可以达成目的,但是显然效率实在太低。为什么呢?因为我们使用了太多没用的信息,我的祖先是谁与我父亲是谁没什么关系,这样一层一层找太浪费时间,不如我直接当祖先的儿子,问一次就可以出结果了。甚至祖先是谁都无所谓,只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ,这就是路径压缩。——OI-Wiki

代码

int n, p[N];
void init()//初始化
{
    for(int i = 1; i <= n; i++) p[i]=i;
}
int find(int x)//查询x的集合编号
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y)//合并xy所在集合
{
    x = find(x), y = find(y);
    if(x == y) return;
    p[x] = y;
}

扩展

维护size的并查集

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化,假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合:
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

维护到祖宗节点距离的并查集

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化,假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合:
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

CF731C-Socks

描述

有n只袜子,k种颜色,给定每只袜子的颜色,在m天中,问最少修改几只袜子的颜色,可以使每天要穿的袜子颜色相同。

题解

用并查集维护需要保证是同一个颜色的集合,由题意,同一天的两个编号必定在同一个集合内。

而后统计每个集合内哪一个颜色的数量最多,集合的大小减去最大的数量即为这个集合需要修改的数量。

将所有集合的贡献累加即为答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int p[N], c[N], cnt[N], n, m, k;
vector<int> v[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        scanf("%d", &c[i]);
    }
    for (int i = 1, l, r; i <= m; i++)
    {
        scanf("%d%d", &l, &r);
        int pl = find(l), pr = find(r);
        if (pl != pr)
            p[pl] = pr;
    }

    for (int i = 1; i <= n; i++)
    {
        int tmp = find(i);
        v[tmp].push_back(c[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int tn = v[i].size(), mx = 0;
        if (!tn)
            continue;
        for (int j = 0; j < tn; j++)
        {
            cnt[v[i][j]]++;
            mx = max(mx, cnt[v[i][j]]);
        }
        for (int j = 0; j < tn; j++)
            cnt[v[i][j]]--;
        res += tn - mx;
    }
    printf("%d\n", res);
    return 0;
}

CF362D Fools and Foolproof Roads

描述

给定 n 个点 m 条边的无向图,问是否能在图里添加 p 条边使得加边后存在恰好 q 个连通分量,同时请求出边权总和最小的方案。

新增边的边权为 \(min(10^{9}, S+1)\) ,其中 S 为这条边连接的两个联通块的边权之和。

题解

维护一个并查集来表示联通块,由题意要额外维护联通块的大小去计算连边的代价。

判断无解的情况:

  1. 将联通块进行了 p 次连边后依然联通块的数量大于 q
  2. 未连边前联通块数量小于 q
  3. 点的数量为 q ,且不存在边,此时若 p 非0,由于不允许自环,故无解

求最优的方案时,将联通块压入优先队列,每次取最小的两个联通块合并,保证每次合并的边权最小

若还没有用完 p 次连边就已经满足条件,则在任意一联通块内找任意两点,将剩下所有连边加在这两个点上

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10, inf = 1e9;
typedef pair<ll, ll> pii;
ll p[N], w[N], n, m, pp, q, cnt;
struct cmp
{
    bool operator()(const pii p1, const pii p2)
    {
        return p1.first > p2.first;
    }
};
priority_queue<pii, vector<pii>, cmp> blk;
ll find(ll x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
void merge(ll x, ll y, ll l)
{
    ll px = find(x), py = find(y);
    if (px == py)
        w[px] += l;
    else
    {
        p[px] = py;
        w[py] += l + w[px];
        cnt--;
    }
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &pp, &q);
    cnt = n;
    for(ll i = 1; i <= n; i++) p[i] = i;
    for (ll i = 1, x, y, l; i <= m; i++)
    {
        scanf("%lld%lld%lld", &x, &y, &l);
        merge(x, y, l);
    }
    if(cnt - pp > q || cnt < q)
    {
        puts("NO");
        return 0;
    }
    if(!m && !(q - n) && pp)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for (ll i = 1; i <= n; i++)
        if (i == find(i))
            blk.push({w[p[i]], i});
    while (cnt > q)
    {
        pii b1 = blk.top();
        blk.pop();
        pii b2 = blk.top();
        blk.pop();
        pp--, cnt--;
        printf("%lld %lld\n", b1.second, b2.second);
        p[b2.second] = b1.second;
        w[b1.second] += min(inf, b1.first + b2.first + 1) + b2.first;
        blk.push({w[b1.second], b1.second});
    }
    ll ran;
    for(ran = 1; ran <= n; ran++) if(find(ran) != ran) break;
    while(pp--) printf("%lld %lld\n", ran, p[ran]);
    return 0;
}

间歇性踌躇满志,持续性混吃等死