做题感悟:这题开始被吓到了,一看是多校练习赛,在 HDU 提交了 n 次都是栈溢出,但是在 POJ 1 A.(哪位大牛路过麻烦看一下挫代码为什么在POJ上可以过在HDU上过不了)真无语!!
解题思路:方法一、先说我的思路吧: 题意中 M x y 是把 y 接到 x的下面,最后求 x下面有多少个木块,其实可以转化为把y 放到x上面,进而求x上面有多少个。但是这样的话必须开两个并查集, 假如 M 1 6 M 2 4 M 2 6 查询C 4 答案为 2 可以用一个并查集fa[] fa[1‘]=6’ (1‘,6'均指其父亲) fa[2']=4' (这个并查集起主要作用)如果你要实现 M
2 6 必须找到2的父亲和6的最小的孙子让6最小的孙子成为2父亲的父亲(简单说就是让2的父亲接在6的孙子后面),至于查询的时候 执行一次并查集就可以得到x上面有多少个(题中是下面有多个).
方法二、其实可以用一个数组记录节点总的个数(这样HDU可以过)其它上面的差不多具体见这里~>.
代码:
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define LEN sizeof(struct node) const double PI = 3.1415926 ; const double INF = 99999999 ; const int MX =30005 ; int fa[MX],fb[MX],num[MX] ; int FA(int x) { if(fa[x]!=x) { int y=FA(fa[x]) ; num[x]+=num[fa[x]] ;// 更新权值 return fa[x]=y ; } else return x ; } int FB(int x) // 寻找子节点 { return fb[x]==x ? x : fb[x]=FB(fb[x]) ; } void init() // 初始化 { for(int i=0 ;i<=30001 ;i++) { fa[i]=i ; fb[i]=i ; num[i]=0 ; } } int main() { char ch ; int m,x,y,ax,ay ; scanf("%d",&m) ; init() ; for(int i=0 ;i<m ;i++) { cin>>ch ; if(ch=='M') { scanf("%d%d",&x,&y) ; if(x!=y) { ax=FA(x) ; // 找子节点 ay=FB(y) ; // 找父亲节点 if(ax!=ay) { fa[ax]=ay ; // 用于查询 num[ax]++ ; // 不要忘记!! fb[ay]=ax ; } } } else { scanf("%d",&x) ; FA(x) ; printf("%d\n",num[x]) ; } } return 0 ; }