UVA 11987 Almost Union-Find （单点修改的并查集）

此题最难处理的操作就是将一个单点改变集合，而普通的并查集是不支持这种操作的。

当结点p是叶子结点的时候，直接pa[p] = root(q)是可以的，

p没有子结点，这个操作对其它结点不会造成任何影响，

而当p是父结点的时候这种操作会破坏子节点的路径，因此必须保留原来的路径。

我们希望pa[p] = root(q)的同时又保留原来的路径，那么只需要在点上做一个标记，

如果这个点被标记，就沿着新的路径寻找。

此时在修改操作的时候这个点一定是叶子结点，所以可以直接pa[p] = root(q)，

而原来的点则变成一个虚点用来保留了原来的路径。

改变集合的操作以及查询都只涉及到单点，这个标记只影响这个点，在二次以及以上的寻找还是要按照原来的路径。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+;

int fa[maxn],fa2[maxn],cnt[maxn],sum[maxn];

bool fg[maxn];

int Find(int x,bool d) {

    if(fg[x]&&d) return Find(fa2[x],false);

    return x==fa[x]?x:fa[x]=Find(fa[x],false);

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n,m;

    while(~scanf("%d%d",&n,&m)){

        for(int i = ; i <= n; i++) fa[i]=i,fg[i]=false,cnt[i]=,sum[i]=i;

        while(m--){

            int op,p,q; scanf("%d%d",&op,&p);

            if(op!=){

                scanf("%d",&q);

                int x = Find(p,true), y = Find(q,true);

                if(op == ){

                    if(x!=y){

                        cnt[y] += cnt[x];

                        sum[y] += sum[x];

                        fa[x] = y;

                    }

                }else {

                    if(x!=y){

                        cnt[x]--,sum[x]-=p;

                        cnt[y]++,sum[y]+=p;

                        fg[p] = true;

                        fa2[p] = y;

                    }

                }

            }else {

                int x = Find(p,true);

                printf("%d %d\n",cnt[x],sum[x]);

            }

        }

    }

    return ;

}

巴特西

UVA 11987 Almost Union-Find （单点修改的并查集）

最新文章

热门文章