当前位置: 代码迷 >> 综合 >> POJ1988-并查集
  详细解决方案

POJ1988-并查集

热度:83   发布时间:2024-01-18 01:05:30.0

题意:有几个stack,初始里面有一个cube。支持两种操作:1.move x y: 将x所在的stack移动到y所在stack的顶部。2.count x:数在x所在stack中,在x之下的cube的个数

题解:构建并查集,在合并和查找集合的过程中更新数量

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std ;
#define MAX 30005
int parent[MAX] ;
int sum[MAX] ;//存储栈中一共有多少元素
int bnum[MAX] ;//存储x之下有多少个元素
void make_set(int x)
{parent[x] = x ;bnum[x] = 0 ;sum[x] = 1 ;
}
int find_set(int x)
{int temp = parent[x];if(parent[x] != x){parent[x] = find_set(parent[x]) ;bnum[x] += bnum[temp] ;}return parent[x] ;
}
void union_set(int x , int y)
{x = find_set(x) ;y = find_set(y) ;parent[x] = y ;bnum[x] += sum[y] ;sum[y] += sum[x] ;
}
int main()
{int T ;cin >> T ;getchar() ;for(int i = 0 ; i < MAX ; i ++) make_set(i) ;while(T --){char request ;int a , b ;scanf("%c " ,&request) ;//cout << request << endl ;if(request == 'M'){scanf("%d%d" , &a , &b) ;getchar() ;//cout << a << ' ' << b <<endl;union_set(a , b) ;}if(request == 'C'){scanf("%d" , &a) ;//cout << a << endl ;getchar() ;find_set(a) ;cout << bnum[a]<<endl ;}}return 0;
}


  相关解决方案