东莞网站制作模板,CP网站开发制作H5,外贸网站源码 php,山东个人网站备案题目背景
NOIP2015 Day1T2
题目描述
有 n 个同学#xff08;编号为 1 到n#xff09;正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象#xff0c;其中#xff0c;编号为 i 的同学的信息传递对象是编号为 Ti 的同学。
游戏开始时#xff0c;每人都…题目背景
NOIP2015 Day1T2
题目描述
有 n 个同学编号为 1 到n正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象其中编号为 i 的同学的信息传递对象是编号为 Ti 的同学。
游戏开始时每人都只知道自己的生日。之后每一轮中所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象注意可能有人可以从若干人那里获取信息但是每人只会把信息告诉一个人即自己的信息传递对象。当有人从别人口中得知自己的生日时游戏结束。请问该游戏一共可以进行几轮
题目限制 输入格式 输出格式
共一行一个整数表示游戏一共可以进行多少轮。
输入输出样例 解题思路
把每个同学看成一个点信息的传递就是在他们之间连有向边游戏轮数就是求最小环
AC代码
#include bits/stdc.h
using namespace std;
int n,Min,last;
int f[200005],d[200005];
int F(int x);
void check(int a,int b);
int main()
{int t;Min0x7777777;cinn;for(int i1;in;i)f[i]i;for(int i1;in;i){cint;check(i,t);}coutMin;return 0;
}void check(int a,int b)
{int xF(a),yF(b);if (x!y){f[x]y;d[a]d[b]1;} //若不相连则连接两点更新父节点和路径长。elseMinmin(Min,d[a]d[b]1); //若已连接则更新最小环长度
}int F(int x)
{if(f[x]!x){int lastf[x];f[x]F(f[x]);d[x]d[last];}return f[x];
}
