首页 > 代码库 > POJ 1988 Cube Stacking 并查集
POJ 1988 Cube Stacking 并查集
题目链接：http://poj.org/problem?id=1988
思路：并查集的扩展~， 感觉并查集里面很多都有用到当前点到祖先的距离。。 。。 这个题目要这么做，记录每个集合的元素个数，然后记录当前元素是第几个被插入到集合中的，其中涉及到了路径压缩。。最后的结果就是总的个数减去第几个被插入到集合。
#include <iostream>#include <cstdio>using namespace std;int n;int f[30020];int sum[30020];int num[30020];int getf(int a){ if(f[a] == a) { return a; } int t = f[a]; f[a] = getf(f[a]); num[a] += num[t]; return f[a];}void merge(int a, int b){ int x = getf(a); int y = getf(b); if(x != y) { f[y] = x; num[y] += sum[x]; sum[x] += sum[y]; }}void init(){ for(int i=1; i<=30010; i++) { f[i] = i; num[i] = 0; sum[i] = 1; }}int main(){ char s[2]; int a,b; while(cin>>n) { init(); for(int i=1; i<=n; i++) { scanf("%s",s); if(s[0] == ‘M‘) { scanf("%d %d",&a, &b); merge(a,b); } else if(s[0] == ‘C‘) { scanf("%d",&a); printf("%d\n", sum[getf(a)]-num[a]-1); } } } return 0;}
POJ 1988 Cube Stacking 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。