洛谷P2661 信息传递 带权并查集
洛谷P2661 信息传递 带权并查集题目描述有 nn 个同学(编号为 11 到 nn )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 ii 的同学的信息传递对象是编号为 T_iTi 的同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息...
洛谷P2661 信息传递 带权并查集题目描述有 nn 个同学(编号为 11 到 nn )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 ii 的同学的信息传递对象是编号为 T_iTi 的同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息...
题目链接题目描述现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度#include<iostream> #include<algorithm> using namespace std; const int maxn = 1e6+5; int fa[maxn]; int child[maxn]; int vis[maxn]; ...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1325题目大意:给你n对数a、b。表示a是b的父亲节点,遇到a==0 && b==0 时结束。然后根据当前信息,判断是否能构成一棵树。思路:然后注意三点就行了。1.树只有一个根节点。2.不能构成一个环状3.父亲节点可以指向多个孩子节点,但是一个孩子节点不能被多个父亲节点所指然后,弄一个flag=0...
洛谷P1551 亲戚 并查集 模板题题目背景若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。题目描述规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。输入格式第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=50...
hdu1232 畅通工程 并查集某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随...