USACO2004 cube stacking /// 带权并查集 oj1302

题目大意：

以N ( 1 ≤ N ≤ 30,000 )个堆栈开始，每个堆栈包含一个单独的立方体。执行P（1≤ P ≤100,000）的操作。

有两种类型的操作：移动和计数。

*在移动操作中，将包含方块X的堆栈移动到包含方块Y的堆栈顶部。

*在计数操作中，在包含立方体X的堆栈中计算立方体X之上的立方体数量并报告该值。

编写一个可以验证游戏结果的程序。

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers:X and Y. For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input.

Sample Input

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

Sample Output

1
0
2

#include <bits/stdc++.h>
using namespace std;
int root[30005],cnt[30005],dis[30005];
int get(int n)
{
    if(root[n]==n) return n;
    int temp=root[n];
    root[n]=get(root[n]);  ///递归的同时路径压缩 否则cnt连加时会重复
    cnt[n]+=cnt[temp];        ///用cnt记录高度
    return root[n];
}
void mope()
{
    int m,n;
    scanf("%d%d",&m,&n);
    int gm=get(m),gn=get(n);
    if(gm==gn) return;
    root[gm]=gn;
    cnt[gm]=dis[gn];         ///用dis记录根的高度       
    dis[gn]+=dis[gm];
    dis[gm]=0;
}
int main()
{
    for(int i=0;i<30005;i++)
    {
        root[i]=i;
        cnt[i]=0;
        dis[i]=1;
    }
    int p; scanf("%ld",&p);
    while(p--)
    {
        getchar();
        char ope;
        scanf("%c",&ope);
        if(ope=='M') mope();
        else if(ope=='C')
        {
            int n; scanf("%ld",&n);
            get(n);    //调用get()更新一下cnt的值
            printf("%ld
",cnt[n]);
        }
    }

    return 0;
}

View Code

还没找出为什么用递归方式实现的并查集可以AC

而下面非递归的方式就过不了

#include <bits/stdc++.h>
using namespace std;
int root[30005],cnt[30005],dis[30005];
int get(int n)
{
    int dal=n;
    while(root[dal]!=dal)
    {
        cnt[dal]+=cnt[root[dal]];
        dal=root[dal];
    }

    int t,odal=n;
    while(root[odal]!=dal)
    {
        t=root[odal];
        root[odal]=dal;
        odal=t;
    }
    return dal;
}
void mope()
{
    int m,n;
    scanf("%d%d",&m,&n);
    int gm=get(m),gn=get(n);
    if(gm==gn) return;
    root[gm]=gn;
    cnt[gm]=dis[gn];
    dis[gn]+=dis[gm];
    dis[gm]=0;
}
int main()
{
    for(int i=0;i<30005;i++)
    {
        root[i]=i;
        cnt[i]=0;
        dis[i]=1;
    }
    int p; scanf("%d",&p);
    while(p--)
    {
        getchar();
        char ope;
        scanf("%c",&ope);
        if(ope=='M') mope();
        else if(ope=='C')
        {
            int n; scanf("%d",&n);
            get(n);
            printf("%d
",cnt[n]);
        }
    }

    return 0;
}

View Code