网站上的搜索怎么做,帝国生成网站地图,济南互联网网络营销,湖北营销型网站建设【题目描述】 约翰和贝西在叠积木。共有30000块积木#xff0c;编号为1到30000。一开始#xff0c;这些积木放在地上#xff0c;自然地分成N堆。贝西接受约翰的指示#xff0c;把一些积木叠在另一些积木的上面。一旦两块积木相叠#xff0c; 彼此就再也不会分开了#xf…【题目描述】 约翰和贝西在叠积木。共有30000块积木编号为1到30000。一开始这些积木放在地上自然地分成N堆。贝西接受约翰的指示把一些积木叠在另一些积木的上面。一旦两块积木相叠 彼此就再也不会分开了所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作操作分为两种 第一种是移动操作格式为“移动X到Y的上面”。X和Y代表两块积木的编号意思是将X所的那堆积木整体叠放到Y所在的那堆积木之上 第二种是统计操作格式为“统计Z下方的积木数量”。Z代表一块积木的编号意思是贝西需要报告在编号为Z的积木之下还有多少块积木 请编写一个程序帮助贝西回答每条统计问题。 【输入描述】 第一行一个整数P(1 ≤ P ≤ 10^5) 第二行到第P1行每行描述一条命令如果这行开头的字母是M代表一条移动命令后面的两个整数代表上文中的X和Y如果开头字母是C代表一条统计命令。后面的整数代表上文中的Z保证所有的移动命令都有意义X和Y不会已经出现在同一堆积木里。 【输出描述】 对每一个统计命令输出正确回答用换行符分开每个查询的结果 【输入样例】6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4 【输出样例】1 0 2 【数据范围及提示】 第一次查询时1下面只有一个6第二次查询时3下面没有任何积木第三次查询时4下面有两块积木1和6。 源代码#includecstdio
#includeiostream
using namespace std;
int n,f[30001],top[30001],sum[30001];
int Find(int t)
{if (f[t]t)return t;int Tf[t];f[t]Find(T);top[t]top[T];sum[t]sum[T];return f[t];
}
int Merge(int t1,int t2)
{int T1Find(t1);int T2Find(t2);f[T1]T2;Find(top[T2]);sum[T1]sum[top[T2]]1;top[T2]top[T1];
}
int main()
{scanf(%d,n);for (int a1;a30000;a)top[a]f[a]a;for (int a1;an;a){char T;cinT;if (TM){int t1,t2;scanf(%d%d,t1,t2);Merge(t1,t2);}else{int t;scanf(%d,t);Find(t);printf(%d\n,sum[t]);}}return 0;
} 转载于:https://www.cnblogs.com/Ackermann/p/5756625.html
