首页 > 代码库 > 带权值得并查集

带权值得并查集

2024-11-02 18:40:39   205人阅读

Building Block

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 151   Accepted Submission(s) : 57

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

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

Sample Output

102

Source

2009 Multi-University Training Contest 1 - Host by TJU
 
题意：

  M x y把x的管放在y管的上面

 C x求x的下面有多少个砖块

down[i]表示i到根节点之间有多少块砖，再维护一个sum[x]数组，表示管x上一共串有多少个砖块

find每次更新down数组；

#include<iostream>#include<stdio.h>using namespace std;int par[30005];int sum[30005];//上面有多少；int down[30005];int findi(int x){    if(x==par[x])        return x;    int p=findi(par[x]);    down[x]=down[par[x]]+down[x];    return par[x]=p;}void unioni(int x,int y){    int xx=findi(x);    int yy=findi(y);    if(xx!=yy)    {        par[xx]=yy;        down[xx]=sum[yy];        sum[yy]=sum[yy]+sum[xx];    }}int main(){int n;for(int i=0;i<30005;i++)    sum[i]=1;for(int i=0;i<30005;i++)    down[i]=0;for(int i=0;i<30005;i++)     par[i]=i;scanf("%d",&n);while(n--){    char a;    cin>>a;    if(a==‘M‘)    {        int b,c;       scanf("%d%d",&b,&c);        unioni(b,c);    }    if(a==‘C‘)    {        int d;         scanf("%d",&d);         findi(d);         printf("%d\n",down[d]);    }}    return 0;}

 

 

带权值得并查集


联系
我们