浙江财经大学
信息管理与工程学院

HDU 2818 Building Block(带权并查集)

本文由 Ocrosoft 于 2016-07-24 22:50:30 发表

Building Block

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4884    Accepted Submission(s): 1511

Problem Description
John are playing with blocks. There are N blocks (1 <= N <= 30000) numbered 1…N。Initially, there are N piles, and each pile contains one block. Then John do some operations P times (1 <= P <= 1000000). There are two kinds of operation:
M X Y : Put the whole pile containing block X up to the pile containing Y. If X and Y are in the same pile, just ignore this command. 
C X : Count the number of blocks under block X 
You are request to find out the output for each C operation.
 

Input
The first line contains integer P. Then P lines follow, each of which contain an operation describe above.
 

Output
Output the count for each C operations in one line.
 

Sample Input
	
6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4
 

Sample Output
	
1 0 2
 

Solution

M a b 表示将包含a的方块放到包含b方块上(都是往上放的)。

C a 是询问a的方块下面有多少方块(不含a)。

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 30000+10
using namespace std;
int pre[MAXN],r[MAXN],m[MAXN];
int find(int x)
{
    if(pre[x]!=x)
    {
        int p=pre[x];
        pre[x]=find(p);
        r[x]+=r[p];
    }
    return pre[x];
}
void Union(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
    {
        pre[fx]=fy;
        r[fx]+=m[fy]+1;
        m[fy]+=m[fx]+1;
    }
}
void init()
{
    ms(r),ms(m);
    for(int i=0; i<MAXN; i++)pre[i]=i;
}
int main()
{
    int n,a,b;
    char c;
    while(cin>>n)
    {
        init();
        while(n--)
        {
            cin>>c;
            if(c=='M')
            {
                int a,b;
                cin>>a>>b;
                Union(a,b);
            }
            else
            {
                cin>>a;
                find(a);
                printf("%d\n",r[a]);
            }
        }
    }
    return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 2818 Building Block(带权并查集)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址