【zz】并查集

http://blog.sina.com.cn/s/blog_4c396f430100cort.html

嗯……最近好好学了下并查集……以弥补我远不过关的数据结构……（其实学了并查集我的数据结构还是远不过关……）

首先要说的是……我现在才学会的东西，逆铭大牛牛早在几年前就学会了……大家可以参考他的博客 ……

那么，并查集是一种对不相交集合的数据结构，它支持两种操作：

• 合并两个集合
• 查找一个元素属于哪个集合

通常并查集可以用森林或者是链表来实现，但是通常链表实现效率不如森林实现，所以通常使用并查集的森林实现，这时，每个集合其实就是一棵树，并且这个集合就用这颗树的树根来标识。

可以用数组来表示森林，用p[i]表示结点i的父结点。初始的时候让每个结点的父结点指向其自身，即p[i] = i，每个结点就是一个单独的集合。那么合并两个元素x,y所在的集合，就可以先把x和y所在集合的标识，即其树根计算出来，设为p_x,p_y，然后再让p_y的父结点指向p_x即可，即p[p_y] = p_x。下面的函数合并了两个元素x,y所在的集合：

void union_set(int x, int y) {
    int p_x = get_parent (x), p_y = get_parent(y);
    p[p_y] = p_x;
}

 在查找一个元素属于哪个集合，即查找这个元素的根结点的时候，如果这个元素的父结点就是其自身，即这个元素本身就是根结点，那么查找结束，返回其本身。否则返回这个元素父结点的根结点。这里有一个称为路径压缩的优化，就是在查找这个元素的根结点时，把其到根结点的路径上的所有点都直接连接到根结点上，可以防止树退化成链。所以可以用递归来实现（不用递归效率更高，读者可以尝试自行完成……）。下面的函数返回结点k的根结点，同时进行路径压缩：

int get_parent(int k) {
    return p[k] == k ? k : (p[k] = get_parent(p[k]));
}

 还有一个优化叫做按秩合并，就是总是在合并两个集合的时候总是把深度小的树合并到深度大的树里面，以防止树退化成链。这里我没有提供代码（其实代码也相当简单），具体请大家参考CLRS……

综上，并查集的实现可以是如下的代码：

struct uf_set {
    int p[0xffff];
    void clear() {
        for (int i = 0; i < 0xffff; ++i)
            p[i] = i;
    }
    int get_parent(int k) {
        return p[k] == k ? k : (p[k] = get_parent(p[k]));
    }
    void union_set(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        p[p_y] = p_x;
    }
};

有关并查集更详细的内容请参考CLRS或者黑书……下面说三道题目：

• POJ 1611 The Suspects

这个题没什么说的了，就是最裸的并查集，统计与0属于同一个集合的结点数即可。

代码如下：

#include <cstdio>

using namespace std;

struct uf_set {
    int p[30000];
    void clear() {
        for (int i = 0; i < 30000; ++i)
            p[i] = i;
    }
    int get_parent(int k) {
        return p[k] == k ? k : (p[k] = get_parent(p[k]));
    }
    void union_set(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        p[p_y] = p_x;
    }
};

int n, m, ans;
uf_set union_find_set;

int main() {
    for (scanf("%d%d", &n, &m); n != 0; scanf("%d%d", &n, &m)) {
        union_find_set.clear();
        for (int i = 0, num, id1, id2; i < m; ++i) {
            scanf("%d%d", &num, &id1);
            for (int j = 1; j < num; ++j) {
                scanf("%d", &id2);
                union_find_set.union_set(id1, id2);
            }
        }
        int group0 = union_find_set.get_parent(0);
        ans = 0;
        for (int i = 0; i < n; ++i)
            if (union_find_set.get_parent(i) == group0)
                ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

• CEOI 1999 / POJ 1733 Parity game / URAL 1003 Parity

这个题是并查集的扩展。可以这样考虑：如果[s, t]这个区间内数的和为even，那么表示[0, s - 1]和[0, t]（简记为s - 1和t）是奇偶性相同的，反之就是奇偶性不同的。但是我们在处理这个问题的时候没有必要像处理一般并查集问题一样把奇偶性相同的合并，把奇偶性不同的处理 为不同的集合。而是把所有已经发生了关系的集合都统统合并，并为每个元素都增加一个域p_r[i]表示结点i与其父亲结点（p[i]）的关系是 p_r[i]，p_r[i] = 1表示其与父结点的奇偶性相同，p_r[i] = 0表示奇偶性不同。那么只需要稍微思考一下在合并集合的时候（有两种：一种是奇偶性相同的集合合并，一种是奇偶性不同的集合合并）怎么维护p_r域就可以 了。还需要注意的是因为lenth太大（最大为1000000000），而questions and answers比较小（最大为5000），所以需要在读入数据以后进行离散化（当然是离散化三部曲：sort、unique、lower_bound 了！）。具体的实现细节请参考代码。

代码如下（URAL的）：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct question {
    int s, t;
    char f;
};

struct uf_set {
    int p[10000], p_r[10000];
    void clear() {
        for (int i = 0; i < 10000; ++i) {
            p[i] = i;
            p_r[i] = 1;
        }
    }
    int get_parent(int k) {
        if (p[k] == k)
            return k;
        int tmp = get_parent(p[k]);
        p_r[k] = 1 ^ p_r[p[k]] ^ p_r[k];
        return p[k] = tmp;
    }
    bool set_same(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        if (p_x == p_y)
            return p_r[x] == p_r[y];
        p[p_y] = p_x;
        p_r[p_y] = 1 ^ p_r[x] ^ p_r[y];
        return true;
    }
    bool set_diff(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        if (p_x == p_y)
            return p_r[x] != p_r[y];
        p[p_y] = p_x;
        p_r[p_y] = p_r[x] ^ p_r[y];
        return true;
    }
};

int l, n, num[10000], ans;
question q[5000];
uf_set union_find_set;

int main() {
    char buf[10];
    for (scanf("%d", &l); l != -1; scanf("%d", &l)) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d%d%s", &q[i].s, &q[i].t, buf);
            --q[i].s;
            q[i].f = buf[0];
            num[i * 2] = q[i].s;
            num[i * 2 + 1] = q[i].t;
        }
        sort(num, num + n * 2);
        l = unique(num, num + n * 2) - num;
        for (int i = 0; i < n; ++i) {
            q[i].s = lower_bound(num, num + l, q[i].s) - num;
            q[i].t = lower_bound(num, num + l, q[i].t) - num;
        }
        union_find_set.clear();
        for (ans = 0; ans < n; ++ans) {
            if (q[ans].f == 'e') {
                if (!union_find_set.set_same(q[ans].s, q[ans].t))
                    break;
            } else if (q[ans].f == 'o') {
                if (!union_find_set.set_diff(q[ans].s, q[ans].t))
                    break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

• NOI 2001 / POJ 1182 食物链

同样是并查集的扩展，和上一题目差不多，只不过p_r[i]有三种取值了：p_r[i] = 0表示种类相同，p_r[i] = 1表示i吃i的父结点，p_r[i] = -1表示i被i的父结点吃。只需要搞清楚合并集合以后p_r的取值就可以了。

代码如下：

#include <cstdio>
#include <cstring>

using namespace std;

struct uf_set {
    int p[50000], p_r[50000];
    void clear() {
        for (int i = 0; i < 50000; ++i) {
            p[i] = i;
            p_r[i] = 0;
        }
    }
    int get_relation(int x, int y) {
        if (x == -1 && y == -1)
            return 1;
        if (x == 1 && y == 1)
            return -1;
        return x + y;
    }
    int get_parent(int k) {
        if (p[k] == k)
            return k;
        int tmp = get_parent(p[k]);
        p_r[k] = get_relation(p_r[k], p_r[p[k]]);
        return p[k] = tmp;
    }
    bool set_same(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        if (p_x == p_y)
            return p_r[x] == p_r[y];
        p_r[p_y] = get_relation(-p_r[y], p_r[x]);
        p[p_y] = p_x;
        return true;
    }
    bool set_eat(int x, int y) {
        int p_x = get_parent(x), p_y = get_parent(y);
        if (p_x == p_y)
            return get_relation(p_r[x], -p_r[y]) == 1;
        p_r[p_y] = get_relation(-p_r[y], get_relation(-1, p_r[x]));
        p[p_y] = p_x;
        return true;
    }
};

int n, m, ans;
uf_set union_find_set;

int main() {
    scanf("%d%d", &n, &m);
    union_find_set.clear();
    for (int i = 0, d, x, y; i < m; ++i) {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n) {
            ++ans;
            continue;
        }
        if (d == 1) {
            if (!union_find_set.set_same(x - 1, y - 1))
                ++ans;
        } else if (d == 2) {
            if (!union_find_set.set_eat(x - 1, y - 1))
                ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

发现写ACM相关的东西好累的说……希望对大家有用……