并查集不多的习题及其思路

Ameiyo · 2019-04-09 12:01:14 · 个人记录

并查集不多的习题及其思路

made\ by\ Ameiyo

普通并查集
带权并查集
扩展域并查集

普通并查集

没什么好讲的。

带权并查集

挺重要的一种并查集，一般配合上路径压缩代码如下:

int fa[N], dis[N];
int Find(int x) {
    if (x == fa[x]) return fa[x];
    int t = fa[x]; fa[x] = Find(fa[x]);
    if (t != fa[x]) dis[x] += dis[t];
    return fa[x];
}

扩展域并查集

也算挺重要的吧，差不多算是给每个节点几个虚拟节点，代表其不同的身份，可以用来判断正误之类的东西。

Vjudge练习

A

普通并查集，YY向。某个点离开集合时，其儿子仍然在里面，因此要开一个新的虚拟节点代表现在的他。

B

带权并查集，直接维护即可，可参见洛谷P1196银河英雄传说。

C

食物链，经典题目，两种做法:

扩展域并查集分别用 X1 X2 X3 表示 X 的三种身份，可以理解为三个平行世界，但是这三个世界中，他们身份之间的关系是相对一样的。因为已知只有三种，而且三种之间关系固定，那么得到 X 吃 Y 时，X1 吃 Y1，X2 吃 Y2，X3 吃 Y3，所以就有 X1 Y3, X2 Y1, X3 Y2 分别是同类。当有人说两个同类互相吃时，就肯定是假话啦。

带权并查集代码量稍短，效率略高。因为三者关系是一个循环，所以可以用 0 表示 x 与其 father 同种，用 1 表示 x 吃其 father ，用 2 表示 x 被其 father 吃。这样路径压缩时 dis 相加后对 3 取余即可，可以发现这样维护并不会乱套。合并时我们将 fa[fx] = fy, 那么 dis[x] + dis[fx] + (3 - dis[y]) = tmp(题目给出关系) ，这里用 3 减去是因为关系的相对性。

分别给出代码。

扩展域:

while (k--) {
    int x = read<int>(), y = read<int>(), z = read<int>();
    if (y>n||y<1||z>n||z<1) ++ans;
    else if (x&1) {
        // y and z
        if ( find(y) == find(z+n) || find(z) == find(y+n) ) ++ans; // 吃 或 被吃
        else {
            union_set(y, z);
            union_set(y+n, z+n);
            union_set(y+n+n, z+n+n);
        }
    } else {
        // y eat z
        if ( find(y) == find(z) || find(z) == find(y+n) ) ++ans; // 同类 或 被吃
        else {
            union_set(y, z+n);
            union_set(y+n, z+n+n);
            union_set(y+n+n, z);
        }
    }
}

带权:

int n, m;
int fa[N], dis[N];

inline int MOD(reg int x) {
    return (x % 3 + 3) % 3;
}

int Findfa(int x) {
    if (fa[x] == x) return x;
    int t = fa[x]; fa[x] = Findfa(fa[x]);
    dis[x] = (dis[x] + dis[t]) % 3;
    return fa[x];
}

int main() {
    n = read<int>(), m = read<int>();
    int Ans = 0;
    for (reg int i = 1; i <= n; ++i) fa[i] = i, dis[i] = 0;
    for (reg int i = 1, opt, a, b; i <= m; ++i) {
        opt = read<int>(), a = read<int>(), b = read<int>();
        if (a > n || b > n) { ++Ans; continue; }
        Findfa(a), Findfa(b);
        if (fa[a] == fa[b]) Ans += (MOD(dis[a] - dis[b]) != opt - 1);
        else dis[fa[a]] = MOD(dis[b] - dis[a] + opt - 1), fa[fa[a]] = fa[b];
    } cout << Ans << endl;
    return 0;
}

D

普通并查集，离线反向操作，最后一次抹去标记时将其 father 设为其真正的 father 。

E

普通并查集，启发式合并，每次暴力更新，因为没有拆开来的操作，所以将节点少的合并到节点多的点下面，每次暴力查询即可，因为每次合并节点数都至少增加一倍，所以所有的点因为合并而被遍历到的次数不超过 log(n) (启发式合并，更玄学的可见 [树上启发式合并]())，总复杂度就只有 nlog(n) ，加上优先队列之类的就是 nlog(n) ^ 2 。

F

与食物链类似，但是更水。扩展域，带权都可以。将区间转换为前缀和，区间为偶数端点奇偶性相同，否则不同。直接并查集即可。

G

如果我们按边权从大到小将边两端的顶点一个个合并，那么当加入某条边时，其两端的点都是以他为边权最小统计答案的，每次贪心一下合并即可。

代码:

int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Uni(int x, int y, int w) {
    x = Find(x), y = Find(y);
    if (1ll * w * siz[y] + tot[x] > 1ll * w * siz[x] + tot[y]) {
        fa[y] = x;
        tot[x] += 1ll * w * siz[y];
        siz[x] += siz[y];
    } else {
        fa[x] = y;
        tot[y] += 1ll * w * siz[x];
        siz[y] += siz[x];
    }
}

H

带权并查集 + DP，因为要方案，所以为了 DP 要用带权并查集。

可以发现，当 yes 时，二者身份相同，反之不同。因此最后要找到一种方案只有 m 个人是好人(而且只能有一种方案)。

代码:

int n, p1, p2;
int fa[N], dis[N];

int Find(int x) {
    if (fa[x] == x) return x;
    int t = fa[x]; fa[x] = Find(fa[x]);
    if (t != fa[x]) dis[x] = (dis[x] + dis[t]) & 1;
    return fa[x];
}
void Uni(int x, int y, int opt) {
    int fx = Find(x), fy = Find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
    dis[fx] = (opt ^ dis[x] ^ dis[y]);
}

int f[N][N];
int tp[N], siz[N][2], mark[N], cnt;
bool Work() {
    memset(f, 0, sizeof f);
    memset(siz, 0, sizeof siz);
    f[0][0] = 1, cnt = 0;
    for (reg int i = 1; i <= p1 + p2; ++i) {
        if (Find(i) == i) tp[++cnt] = i;
        ++siz[fa[i]][dis[i]];
    }
    for (reg int i = 1; i <= cnt; ++i) {
        for (reg int j = 0; j <= p1; ++j) {
            if (j >= siz[tp[i]][0]) f[i][j] += f[i-1][j - siz[tp[i]][0]];
            if (j >= siz[tp[i]][1]) f[i][j] += f[i-1][j - siz[tp[i]][1]];
        }
    }
    if (f[cnt][p1] != 1) return false;
    memset(mark, -1, sizeof mark);
    for (reg int i = cnt, j = p1; i; --i) {
        if (f[i-1][j - siz[tp[i]][0]] == 1) {
            mark[tp[i]] = 0;
            j -= siz[tp[i]][0];
        } else if (f[i-1][j - siz[tp[i]][1]] == 1) {
            mark[tp[i]] = 1;
            j -= siz[tp[i]][1];
        }
    }
    return true;
}

int main() {
    while (1) {
        n = read<int>(), p1 = read<int>(), p2 = read<int>();
        if (!n && !p1 && !p2) break;
        for (reg int i = 1; i <= p1 + p2; ++i) fa[i] = i, dis[i] = 0;
        for (reg int i = 1, a, b; i <= n; ++i) {
            char str[10]; str[0] = 0;
            a = read<int>(), b = read<int>();
            while (str[0] == 0) scanf("%s", str);
            if (str[0] == 'y') Uni(a, b, 0);
            else if (str[0] == 'n') Uni(a, b, 1);
            // cout << a << " " << Find(a) << " " << dis[a] << endl;
        }
        if (!Work()) { puts("no"); continue; }
        else for (reg int i = 1; i <= p1 + p2; ++i)
            if (dis[i] == mark[fa[i]]) printf("%d\n", i);
        puts("end");
    }
    return 0;
}

I

带权并查集，令 X[a] = X[fa[a]] + dis[a] ， Y 同理。当一个坦克移动到新的位置时，他的儿子还指着他，所以要开虚拟节点，其他操作根据定义维护或回答即可。

代码 (用 X = INF 表示未知):

int n, m;
int fa[N<<1], dix[N<<1], diy[N<<1]; // 因为有虚拟节点所以要开两倍
int X[N<<1], Y[N<<1], tp[N<<1];
// x[a] = x[fa[a]] + dix[a]
// y[a] = y[fa[a]] + diy[a]

int Find(int x) {
    if (x == fa[x]) return fa[x];
    int t = fa[x]; fa[x] = Find(fa[x]);
    if (t != fa[x]) {
        dix[x] += dix[t], diy[x] += diy[t];
    }
    return fa[x];
}
bool Uni(int x, int y, int dx, int dy) {
    if (Find(x) == Find(y)) { // 同一个对照物也可以比较
        return dix[x] - dix[y] == dx && diy[x] - diy[y] == dy;
    } else if (X[fa[x]] != -INF && X[fa[y]] != -INF) { // 二者都知道
        return X[fa[x]] + dix[x] - X[fa[y]] - dix[y] == dx &&
                Y[fa[x]] + diy[x] - Y[fa[y]] - diy[y] == dy;
    } else {
        dix[fa[x]] = dx + dix[y] - dix[x];
        diy[fa[x]] = dy + diy[y] - diy[x];
        if (X[fa[y]] == -INF && X[fa[x]] != -INF)
            X[fa[y]] = X[fa[x]] - dix[fa[x]], Y[fa[y]] = Y[fa[x]] - diy[fa[x]];
        fa[fa[x]] = fa[y];
        return true;
    }
}

void scan();
int _main() {
    scan();
    int T = read<int>();
    for (int kas = 1; kas <= T; ++kas) {
        printf("Case #%d:\n", kas);
        n = read<int>();
        int cnt = n;
        for (reg int i = 1; i <= n; ++i)
          fa[i] = tp[i] = i, dix[i] = 0, diy[i] = 0, X[i] = Y[i] = -INF;
        for (reg int i = 1, opt, a, b, x, y; i <= n; ++i) {
            opt = read<int>();
            if (opt == 1) {

                // a move to b + (x, y)
                a = read<int>(), b = read<int>(), x = read<int>(), y = read<int>();
                fa[tp[a] = ++cnt] = tp[b], dix[tp[a]] = x, diy[tp[a]] = y;
                X[tp[a]] = -INF, Y[tp[a]] = -INF;

            } else if (opt == 2) {

                // a move to (x, y)
                a = read<int>(), x = read<int>(), y = read<int>();
                tp[a] = ++cnt;
                fa[tp[a]] = tp[a], dix[tp[a]] = 0, diy[tp[a]] = 0;
                X[tp[a]] = x, Y[tp[a]] = y;

            } else if (opt == 3) {

                // a is in b + (x, y)
                a = tp[read<int>()], b = tp[read<int>()], x = read<int>(), y = read<int>();
                if (!Uni(a, b, x, y)) puts("REJECT");

            } else if (opt == 4) {

                // a is in (x, y)
                a = tp[read<int>()], x = read<int>(), y = read<int>();
                if (X[Find(a)] == -INF) {
                    X[fa[a]] = x - dix[a], Y[fa[a]] = y - diy[a];
                } else if (X[fa[a]] + dix[a] != x || Y[fa[a]] + diy[a] != y) puts("REJECT");

            } else if (opt == 5) {

                // a - b
                a = tp[read<int>()], b = tp[read<int>()];
                if (Find(a) == Find(b)) {
                    printf("%d %d\n", dix[a] - dix[b], diy[a] - diy[b]);
                } else if (X[fa[a]] != -INF && X[fa[b]] != -INF) {
                    printf("%d %d\n", X[fa[a]] + dix[a] - X[fa[b]] - dix[b],
                                        Y[fa[a]] + diy[a] - Y[fa[b]] - diy[b]);
                } else {
                    puts("UNKNOWN");
                }

            } else if (opt == 6) {
                // a
                a = tp[read<int>()];
                if (X[Find(a)] == -INF) puts("UNKNOWN");
                else printf("%d %d\n", X[fa[a]] + dix[a], Y[fa[a]] + diy[a]);

            }
        }
    }
    return 0;
}

in\ 2019.4.9