ZOJ 3261 Connections in Galaxy War(union-find-set)

Description

假设有编号从0开始的n个点，每个点都有一个非负权值p[i]。现在有没有重边的m条边和Q个操作。
对于操作有两种类型 :
destroy a b 表示摧毁a,b点之间的边
query a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最小的点。如果没有这样的点输出-1。

Analyze

我所解决不了的问题是删边，并查集没学过删边操作，要是每次都重建一次并查集太耗时间了，怎么办呢？

逆序解决问题：

从后向前解决问题，最初的并查集排除了所有删掉的边，正好对应最后的查询。然后向前遍历，若遇到删边操作，说明前面的查询都是建立在“包含这条边”的基础上的，那么我们添边，如此一来，化“删边”为“添边”，解决了问题。

总结：正序解决问题不行，试试逆序。老子说过：世间万物都包含对立两方，对立的双方可以相互转化。

另外用一个mmax[i]数组记录以i点所在集合(连通块)内最大val值，方法是把mmax数组作为每个集合祖先节点的一个属性，毕竟祖先节点代表着整个集合。

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;

int n, m, k, cnt;
int pre[N], val[N], u[N], v[N], mmax[N], idx[N], ans[N];
map< int, map<int, bool> >mp;

struct node
{
    char s[10];
    int x, y;
}q[N];

int found(int x)
{
    if(pre[x] == -1)
        return x;
    return pre[x] = found(pre[x]);
}

void unite(int a, int b)
{
    int aa = found(a);
    int bb = found(b);
    if(aa != bb)
    {
        pre[aa] = bb;
        if(mmax[bb] < mmax[aa])
        {
            mmax[bb] = mmax[aa];
            idx[bb] = idx[aa];
        }
        else if(mmax[bb] == mmax[aa])
            idx[bb] = min(idx[bb], idx[aa]);
    }
}

int main()
{
    bool flag = 0;
    while(~scanf("%d", &n))
    {
        cnt = 0;
        mp.clear();
        memset(pre, -1, sizeof(pre));

        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &val[i]);
            mmax[i] = val[i];
            idx[i] = i;
        }

        scanf("%d", &m);
        for(int i = 1; i <= m; ++i)
            scanf("%d %d", &u[i], &v[i]);

        scanf("%d", &k);
        for(int i = 1; i <= k; ++i)
        {
            scanf("%s", q[i].s);
            if(q[i].s[0] == 'q')
                scanf("%d", &q[i].x);
            else
            {
                scanf("%d %d", &q[i].x, &q[i].y);
                mp[ q[i].x ][ q[i].y ] = 1;
                mp[ q[i].y ][ q[i].x ] = 1;
            }
        }

        for(int i = 1; i <= m; ++i)
            if(mp[ u[i] ][ v[i] ] == 0)
                unite(u[i], v[i]);

        for(int i = k; i >= 1; --i)
        {
            if(q[i].s[0] == 'd')
                unite(q[i].x, q[i].y);
            else
            {
                int xx = found(q[i].x);
                if(mmax[xx] > val[ q[i].x ])
                    ans[cnt++] = idx[xx];
                else
                    ans[cnt++] = -1;
            }
        }

        if(flag)
            cout << '\n';
        flag = 1;
        for(int i = cnt - 1; i >= 0; --i)
            cout << ans[i] << '\n';
    }
    return 0;
}