首页 > 代码库 > UVALive 6910 Cutting Tree(并查集应用)

UVALive 6910 Cutting Tree(并查集应用)

  总体来说,这个题给的时间比较长,样例也是比较弱的,别的方法也能做出来。

  我第一次使用的是不合并路径的并查集,几乎是一种暴力,花了600多MS,感觉还是不太好的,发现AC的人很多都在300MS之内的过得。

  看到他们的做法后,我知道了这个题比较好的做法。

  逆向思维的并查集,因为这里只有去边操作,完全可以离线计算,把删边当成加边,然后逆序输出答案即可。

  但是,这个却有一个坑,很坑,只有第一次删除的时候,我们才对他进行操作,加边的时候也只能在第一次删除的时候加。当时因为这里,十分困惑……

  这是我无路径压缩的并查集的做法:

  

技术分享
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define N 20005
int n,fa[N];
int Find(int x){
    while(x != fa[x]){
        x = fa[x];
    }
    return x;
}
int main() {
//    freopen("E.in.cpp","r",stdin);
    int T,k,ca=0,p,a,b;
    scanf("%d",&T);
    char op[2];
    while(T--) {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i++) {
            fa[i] = i;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d",&p);
            if(p == 0) fa[i] = i;
            else {
                fa[i] = p;
            }
        }
        printf("Case #%d:\n",++ca);
        while(k--) {
            scanf("%s",op);
            if(op[0] == C) {
                scanf("%d",&b);
                if(fa[b] == b) continue;
                fa[b] = b;
            } else {
                scanf("%d%d",&a,&b);
                if(Find(a) != Find(b)) {
                    printf("NO\n");
                } else printf("YES\n");
            }
        }
    }
    return 0;
}
View Code

  这是逆序离线并查集的做法:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int N = 2e4+5;
int n,fa[N],pa[N],vis[N];
string ans[5005];
struct Query {
    int a,b,kind;
    void Set(int A,int B,int k) {
        a = A;
        b = B;
        kind = k;
    }
} q[5005];
int Find(int x) {
    return fa[x]==x? x :fa[x]=Find(fa[x]);
}
void Union(int a,int b) {
    fa[Find(b)] = Find(a);
}
int main() {
//    freopen("E.in.cpp","r",stdin);
    int T,k,ca=0;
    char op[3];
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i++) {
            scanf("%d",&pa[i]);
            fa[i] = i;
            vis[i] = 0;
        }
        printf("Case #%d:\n",++ca);
        int a,b;
        for(int i = 0; i < k; i++) {
            scanf("%s",op);
            if(op[0] == C) {
                scanf("%d",&a);
                if(pa[a]!=0 && vis[a] != 1) q[i].Set(a,0,1);
                else q[i].Set(a,0,-1);
                vis[a] = 1;
            } else {
                scanf("%d%d",&a,&b);
                q[i].Set(a,b,0);
            }
        }
        for(int i = 1; i <= n; i++) {
            if(vis[i]==1 || pa[i]==0) continue;
            Union(pa[i],i);
        }
        int cnt = 0;
        for(int i = k-1; i >= 0; i--) {
            if(q[i].kind == -1) continue;
            else if(q[i].kind == 0) {
                if(Find(q[i].a) == Find(q[i].b)) ans[cnt++] = "YES";
                else ans[cnt++] = "NO";
            } else  Union(pa[q[i].a],q[i].a);
        }
        for(int i = cnt-1; i >= 0; i--) {
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

 

UVALive 6910 Cutting Tree(并查集应用)