关键词:
题目描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
Thus a professional tree manager is needed. Your task is to write a program to help manage the trees.
Initially, there are n forests and for the i-th forest there is only the i-th tree in it. Given four kinds of operations.
1 u v, merge the forest containing the u-th tree and the forest containing the v-th tree;
2 u, separate the u-th tree from its forest;
3 u, query the size of the forest which contains the u-th tree;
4 u v, query whether the u-th tree and the v-th tree are in the same forest.
输入描述:
The first line contains an integer T, indicating the number of testcases.
In each test case:
The first line contains two integers N and Q, indicating the number of initial forests and the number of operations.
Then Q lines follow, and each line describes an operation.
输出描述:
For each test cases, the first line should be "Case #i:", where i indicate the test case i.
For each query 3, print a integer in a single line.
For each query 4, print "YES" or "NO" in a single line.
示例1
输入
1
10 8
3 1
4 1 2
1 1 2
3 1
4 1 2
2 1
3 1
4 1 2
输出
Case #1:
1
NO
2
YES
1
NO
题意:对trees有四种操作。
1 u v,将包含u-th树的森林和含有v-th树的森林合并在一起;
u,将u-th树与森林分开;
3 u,查询包含u-th树的森林的大小;
4 u v,查询u-th树和v-th树是否在同一林中。
【分析】:给每个点都给他们造一个编号w,删除点,就相当于该点的编号w改变就可以了,也是相当于构造新点。
【出处】:UVA 11987 (白书267)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#define LL long long
#define INF 0xffffff
using namespace std;
const double pi = 2 * acos (0.0);
const int maxn = 2e5+10;
int n,m;
int p[maxn];
int s[maxn];
int w[maxn];
void init()
for(int i=1;i<=maxn;i++) //这里必须是maxn,其他的好像不行
p[i] = i;
w[i] = i;
s[i] = 1;
int Find(int x)
return x==p[x]?x:p[x]=Find(p[x]);
void Union(int x,int y)
int fx = Find(x);
int fy = Find(y);
if(fx!=fy)
p[fx] = fy;
s[fy] += s[fx];
//printf("size=%d\n",s[fy]);
int main()
int T;
cin >> T;
int k =1;
while(T--)
printf("Case #%d:\n",k++);
init();
cin >> n >> m;
int cnt = n;
while(m--)
int op,u,v;
scanf("%d",&op);
if(op==1)
scanf("%d%d",&u,&v);
Union(w[u],w[v]);
else if(op==2)
scanf("%d",&u);
s[Find(w[u])]--;
w[u] = ++cnt;
else if(op==3)
scanf("%d",&u);
printf("%d\n",s[Find(w[u])]);
else
scanf("%d%d",&u,&v);
if(Find(w[u])==Find(w[v]))
printf("YES\n");
else printf("NO\n");
return 0;
第十四届华中科技大学程序设计竞赛--jvarioustree(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网时间限制:C/C++1秒,其他语言2秒空间限制:C/C++32768K,其他语言65536K64bitIOFormat:%lld题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofH 查看详情
第十四届华中科技大学程序设计竞赛cprofessionalmanager并查集删除/虚点(代码片段)
题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Thusaprofessionaltreemanagerisneeded.Yourtaskistowriteaprogramtohelpmanagethetrees.Initially,therearenforestsandforthei-thf 查看详情
第十四届全国大学生智能车竞赛竞赛技术报告下载链接
第十四届智能车竞赛技术报告下载链接 01下载报告 今天上午,看到有同学询问关于十四届智能车竞赛技术报告下载的询问。 实际上,之前第十四届的技术报告在百度上有, 只是没有能够提供下载链接。 由... 查看详情
第十四届华中科技大学程序设计竞赛jvarioustree数值型一维bfs/最小步数(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/J来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.AndtherearemanydifferenttypesoftreesinHUST,eachofwhichhasanumberrepresen 查看详情
浙江财经大学第十四届程序设计竞赛题解
【题面pdf下载】链接:https://pan.baidu.com/s/1Eb16fHtNYMLrRk9QnXWa-g密码:dwn8【题目牛客网提交链接】【现场赛排名】链接:https://pan.baidu.com/s/1jfzH6-7BoPhEjnijGQK53w密码:y669 感谢各位大佬的参赛。 由于命题人水平不高,而且之前没... 查看详情
第十四届华中科技大学程序设计竞赛kwalkingintheforest二分答案/最小化最大值(代码片段)
链接:https://www.nowcoder.com/acm/contest/106/K来源:牛客网题目描述It’suniversallyacknowledgedthatthere’reinnumerabletreesinthecampusofHUST.Nowyou'regoingtowalkthroughalargeforest.ThereisapathconsistingofNsto 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)m.orxzone
链接:https://ac.nowcoder.com/acm/contest/912/M题意:DaenerysStormborn,风暴中出生的丹尼莉丝,theUnburnt,烧不死的,QueenofMeereen,弥林女王,QueenoftheAndalsandtheRhoynarandtheFirstMen,安达尔人,罗伊那人,和先民的女王,LordoftheSevenKingdoms,七国之主 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)h
H.ArithmeticSequence题目链接:https://ac.nowcoder.com/acm/contest/912/H题目数竞选手小r最喜欢做的题型是数列大题,并且每一道都能得到满分。你可能不相信,但其实他发现了一个结论:只要是数列,无论是给了通项还是给了递推式,无论... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)f(代码片段)
F.SuccessionediFixoracci题目链接:https://ac.nowcoder.com/acm/contest/912/F 题目:动态规划(Dynamicprogramming,简称dp)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。例如,假设小x一步能爬1层或2层台阶,求小x爬n... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)b(代码片段)
BBowlingGame题目链接:https://ac.nowcoder.com/acm/contest/912/B题目CUST的队员打完省赛后,小r带着大家去打保龄球。保龄球是一项难度非常高的游戏,然而这根本难不住校队成员,他们个个都很厉害(炸和)一发10个瓶都倒。尤其是小r,每次... 查看详情
长春理工大学第十四届程序设计竞赛(重现赛)j.printout
链接:https://ac.nowcoder.com/acm/contest/912/J题意:小r为了打校赛,他打算去打字社打印一份包含世界上所有算法的模板。到了打字社,小r一看价格:总打印页数X0X0页以下(不含X0X0)x0x0元每页,X0∼X1X0∼X1页(不含X1X1)x1x1元每页,X1&si... 查看详情
hdu6467简单数学题递推公式&&o优化乘法(广东工业大学第十四届程序设计竞赛)(代码片段)
...rce“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛 解题思路: 但是这道题只推出递推 查看详情
广东工业大学第十四届程序设计竞赛鸽子数(代码片段)
ProblemDescription通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很长。通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很长。通常来说,题面短的题目一般都比较难,所以我要把题面写得很长很... 查看详情
(未完成)[hduoj]“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛(代码片段)
solved5 A(签到)题意:两个人随机得到0或1其中之一数字,每个人都可以猜对方的数字是什么,有一个人猜对就算成功,问最优策略下00,01,10,11四种情况两人的成功概率分别是多少。题意不明的签到题,题面说两人不能沟通... 查看详情
湖南大学第十四届acm程序设计新生杯e.easyproblem(代码片段)
E.EasyProblemDescription:Zghhlikesnumber,buthedoesn‘tlikewritingproblemdescription.Sohewilljustgiveyouaprobleminsteadoftellingalongstoryforit.Nowgivenapositiveintegerxandkdigitsa1,a2,...,ak,canyoufindapositiveintegerysuchthatyisthemultipleofxandindecimalrepresentationycontainsalldigitsofa1,a2,...,... 查看详情
第五届湖南省机器人大赛暨第十四届湖南省智能汽车大赛名单(代码片段)
简介:本文汇总了第五届湖南省智能车竞赛的基本信息。感谢中南大学王击老师发送过来的信息。关键词:湖南省智能车竞赛,智能车竞赛#mermaid-svg-Bl4gxd2xsRwJqsTIfont-family:"trebuchetms",verdana,arial,sans-serif;font-size:16px;fill:#3... 查看详情
第十四届蓝桥杯(web应用开发)模拟赛1期-大学组(代码片段)
数据类型检测请看这篇数据类型检测渐变色背景生成器html<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><metahttp-equiv="X-UA-Compatible"content="IE 查看详情
第十四届蓝桥杯c/c++_大学b组省赛真题
...或其它方式提交的答案无效。试题包含“结果填空”和“程序设计”两种题型。结果填空题:要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可,不要书写多... 查看详情