Problem
有n个同学(编号为 1 到 n )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为 Ti的同学。游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
Solution
找出最小的环,由于每个人只会把信息告诉一个人,因此所有环都是无弦环(无弦环: 非相邻节点间不存在边的环 ),也就是说,每个强连通分量都只有一个环,找出最小的强连通分量(不为1)即可。
代码根据题意在Tarjan基础上做了一些简化。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <stdio.h> #include <iostream> #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std;#include <string> #include <stack> #include <map> #include <vector> const int MAXN=200020 ;const int MAXM=200020 ;int n,m,idx,cnt,mn=200020 ;int dfn[MAXN];int low[MAXN];bool instack[MAXN];int a[MAXN];struct E { int u,v,nex; }e[MAXM]; stack<int >s; void Tarjan (int u) { dfn[u]=low[u]=++idx; s.push (u); instack[u]=true ; int v=a[u]; if (!dfn[v]){ Tarjan (v); low[u]=min (low[u],low[v]); } else if (instack[v]){ low[u]=min (low[u],dfn[v]); } if (dfn[u]==low[u]){ int cur,ct=0 ; do { cur=s.top ();s.pop (); instack[cur]=false ; ct++; }while (cur!=u); if (ct>1 ) mn=min (mn,ct); } } int main () { io_opt; cin>>n; int x; for (int i=1 ;i<=n;i++){ cin>>a[i]; } for (int i=1 ;i<=n;i++){ if (!dfn[i]) Tarjan (i); } cout<<mn<<endl; return 0 ; }