并查集

POJ 1182 食物链

添加一个维护当前节点与父节点关系的信息，每次压缩时更新关系，另外join的时候也要根据当前节点和父节点关系以及两个父节点关系更新；

单case，不用EOF处理。

# include <cstdio>
const int maxn = 50005;
int n, k;
int p[maxn];
int g[maxn];
int find(int x) {
    if (x == p[x]) return x;
    int t = find(p[x]);
    g[x] = ((g[p[x]] + g[x]) % 3 + 3) % 3;
    p[x] = t;
    return t;
}
# define testin freopen("in.txt", "r", stdin)
int main()
{
    //while (scanf("%d%d", &n, &k) != EOF) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) p[i] = i, g[i] = 0;
        int ans = 0;
        for (int i = 0, od, x, y; i < k; ++i) {
            scanf("%d%d%d", &od, &x, &y);
            if (x>n||y>n || (od==2 && x==y)) {
                ++ans;
                continue;
            } else {
                int fx = find(x);
                int fy = find(y);
                if (fx != fy) {
                    p[fx] = fy;
                    g[fx] = ((g[y]-g[x]+od-1)%3+3)%3;
                } else if (((g[x]-g[y])%3+3)%3 != od-1){
                    ++ans;
                }
            }
        }
        printf("%d
", ans);
    //}

    return 0;
}

HDU 2473

带删除节点的并查集

对每个节点，映射射到一个虚拟节点，然后对虚拟节点维护并查集，删除节点时，将对应节点应射到一个新的节点即可，由于查询次数有限，浪费的空间可以接受。

# include <cstdio>
const int maxn = 100005;
const int maxm = 1000005;
int n, m;
int fa[maxn + maxm];
bool isRoot[maxn + maxm];
int link[maxn];
int id;
int find(int x) {
    if (x != fa[x]) return fa[x]=find(fa[x]);
}
void join(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x != y) fa[x] = y;
}
void del(int x)
{
    link[x] = id++;
}
# define testin freopen("in.txt", "r", stdin)
int main()
{
    int ica = 0;
    while (scanf("%d%d", &n, &m), n||m) {
        for (int i = 0; i < n+m; ++i) isRoot[i]=false, fa[i]=i;
        for (int i = 0; i < n; ++i) link[i] = i;
        char od[5];
        id = n;
        for (int i = 0, x, y; i < m; ++i) {
            scanf("%s%d", od, &x);
            if (od[0] == 'M') {
                scanf("%d", &y);
                join(link[x], link[y]);
            } else {
                del(x);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!isRoot[ find(link[i]) ]) {
                ++ans;
                isRoot[ find(link[i]) ] = true;
            }
        }
        printf("Case #%d: %d
", ++ica, ans);
    }
    return 0;
}

ZOJ 3261

带删除边的并查集。

WA：维护的并不是树，每个节点和多个节点直接有关系，不能直接删除并查集中的边。

WA 了很多次，原因找到了：再离线保存query处理destroy的情况时，首先保存了query[i][1] = x, 然后条件交换了x,y，然后query[i][2]=y。（x>y时，导致query[i][2]==x）

# include <map>
# include <utility>
# include <algorithm>
# include <cstdio>
# include <cstring>

const int maxn = 10005;
const int maxm = 20005;
const int maxq = 50005;

int n, m, q;
int power[maxn];
int u[maxm], v[maxm];
bool des[maxm];
int query[maxq][3];
int p[maxn];

std::map< std::pair<int, int>, int >mp;

int find(int x) {
    return x==p[x] ? x:p[x]=find(p[x]);
}
void join(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return ;
    if (x > y) std::swap(x, y);
    if (power[x] < power[y]) p[x] = y;
    else p[y] = x;
}
# define testin freopen("in.txt", "r", stdin)
int main()
{
    bool first = true;

    while (scanf("%d", &n) != EOF) {
        mp.clear();
        for (int i = 0; i < n; ++i) scanf("%d", &power[i]);
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &u[i], &v[i]);
            if (u[i] > v[i]) std::swap(u[i], v[i]);
            mp[std::make_pair(u[i], v[i])] = i+1;
        }
        memset(des, false, sizeof(des[0])*m);
        scanf("%d", &q);
        char od[15];
        for (int i = 0, x, y; i < q; ++i) {
            scanf("%s%d", od, &x);
            if (od[0] == 'q') {
                query[i][0] = 0;
                query[i][1] = x;
            } else {
                scanf("%d", &y);
                if (x > y) std::swap(x, y);
                int t = mp[ std::make_pair(x,y) ] - 1;
                if (t >= 0) des[t] = true;
                query[i][0] = 1;
                query[i][1] = x;
                query[i][2] = y;
            }
        }
        for (int i = 0; i < n; ++i) p[i] = i;
        for (int i = 0; i < m; ++i) {
            if (!des[i]) {
                join(u[i], v[i]);
            }
        }
        for (int i = q-1; i >= 0; --i) {
            if (!query[i][0]) {
                int t = find( query[i][1] );
                if (power[t] <= power[ query[i][1] ]) t = -1;
                query[i][2] = t;
            } else {
                join( query[i][1], query[i][2] );
            }
        }
        if (first) first = false;
        else printf("
");
        for (int i = 0; i < q; ++i) {
            if (!query[i][0]) printf("%d
", query[i][2]);
        }
    }

    return 0;
}

cf 356A Knight Tournament

感觉这是一道并查集的好题，记得当时想了很久没思路，赛后看别人的代码也没弄明白。

其实这道题完全体现了并查集的用途：维护集合；不同点在于需要如何维护，即并的方式。

当x打败y时，只要将ans[y]更新为x即可，所以并查集维护的并不是淘汰关系。

将没有淘汰的选手作为根节点，两个未淘汰选手x,y(x<y)之间的淘汰了的选手加入到y的集合中，即当前节点x的根节点是右侧第一个未被淘汰的节点。

# include <stdio.h>
using namespace std;

const int maxn = 300005;

int n, m;
int p[maxn];
int ans[maxn];

int find(int x) {
    return x==p[x] ? x:p[x]=find(p[x]);
}
void join(int l, int r, int x)
{
    while ((l=find(l)) <= r) {
        if(l != x) ans[l] = x, p[l] = l+1;
        ++l;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n+1; ++i) p[i] = ans[i] = i;
    for (int i = 1, x, l, r; i <= m; ++i) {
        scanf("%d%d%d", &l, &r, &x);
        join(l, r, x);
    }
    for (int i = 1; i <= n; ++i) {
        if (i > 1) putchar(' ');
        printf("%d", (ans[i]==i ? 0:ans[i]));
    }
    putchar('
');

    return 0;
}