提高2015信息传递

洛谷 P2661 信息传递（NOIP 提高 2015）

传送门本题本来是一个很好的并查集的题(似乎靠的就是并查集),然而蒟蒻我刚刚学习了 tarjan 所以就用 terjan做了一下大概题意就是:一个人要和另外的一个人告诉他所知道的信息,然后问什么时候他自己的生日可以由一个人那里传回自己这里来. 那么这个一个人向另一个人传递信息,我们可以看成一条有向边. 因为是问什么时候自己的信息可以传回自己这里, 可以自己yy成,一个有向边的环(因为成为一个环,才可以传回自己这里), 那么因为答案求的是有人知道就停止, 那么则是求一个最小的环,所以我们可以求

2015 提高组信息传递--tarjan找最小环

P2661 信息传递题目描述有 n 个同学(编号为 1 到 n )正在玩一个信息传递的游戏.在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学. 游戏开始时,每人都只知道自己的生日.之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象).当有人从别人口中得知自己的生日时,游戏结束.请问该游戏一共可以进行几轮? 输入输出格式输

NOIP 2015 信息传递

kawayi 题目描述有n个同学(编号为1到n)正在玩一个信息传递的游戏.在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学. 游戏开始时,每人都只知道自己的生日.之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象).当有人从别人口中得知自己的生日时,游戏结束.请问该游戏一共可以进行几轮? 输入输出格式输入格式: 输入共2行. 第1行包含1

NOIP2015提高组信息传递 ---并查集问题

题目描述有 n 个同学(编号为 1 到 n )正在玩一个信息传递的游戏.在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti 的同学. 游戏开始时,每人都只知道自己的生日.之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象).当有人从别人口中得知自己的生日时,游戏结束.请问该游戏一共可以进行几轮? 输入输出格式输入格式: 共2行. 第

NOIp 2015信息传递【tarjan/拓扑/并查集】

一道好的NOIp题目,在赛场上总能用许多算法A掉.比如这道和关押罪犯. 题目传送门法一:tarjan在有向图中跑最小环有人从别人口中得知自己信息,等效于出现了一个环.于是这就变成了一个有向图tarjan强连通分量的板子题. #include<cstdio> #include<algorithm> #include<stack> #define maxn 200090 using namespace std; ,dfs_clock,scc_cnt,tong[maxn

[NOIp2015提高组]信息传递

OJ题号:洛谷2661 思路:求最小环.DFS+记忆化. #include<cstdio> #include<cstring> #include<algorithm> int main() { int n; scanf("%d",&n); ],w[n+],s[n+]; memset(s,,sizeof s); ;i<=n;i++) scanf("%d",&t[i]); int ans=0x7fffffff;