Luogu2661 信息传递（图论）
Description
有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？
第1行包含1个正整数n表示n个人。
第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i
的同学的信息传递对象是编号为Ti的同学，Ti≤n且Ti≠i
数据保证游戏一定会结束。
Output
输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。
5 2 4 2 3 1
Sample Output
３
Http
Luogu:https://www.luogu.org/problem/show?pid=2661
Source
图论
解决思路
首先去掉所有入度为０的点，因为它们不可能出现在环上。 然后用vis标记出当前某个点是否在某一环上，如果不是，则循环扫出这个环，全部标记为已访问，并统计个数，取环的大小的最小值，最后这就是解。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxN=200001;
const int inf=2147483647;
int n;
int Edge[maxN];
int InDegree[maxN];
int vis[maxN];
queue<int> Q;
int main()
{
memset(InDegree,0,sizeof(InDegree));
memset(vis,0,sizeof(vis));
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>Edge[i];
InDegree[Edge[i]]++;//统计入度
}
for (int i=1;i<=n;i++)
if (InDegree[i]==0)
{
Q.push(i);
vis[i]=-1;
}
while (!Q.empty())//把所有入度为０的点删掉，这里就是标记为-1
{
int u=Q.front();
Q.pop();
InDegree[Edge[u]]--;
if (InDegree[Edge[u]]==0)
{
vis[Edge[u]]=-1;
Q.push(Edge[u]);
}
}
int Ans=inf;
for (int i=1;i<=n;i++)//找环
if (vis[i]==0)
{
vis[i]=1;
int u=i;
int cnt=1;
while (vis[Edge[u]]==0)
{
u=Edge[u];
vis[u]=1;
cnt++;
}
Ans=min(Ans,cnt);//统计最小值
}
cout<<Ans<<endl;
return 0;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7211657.html
相关资源：精选5篇北京南锣鼓巷导游词_精选.doc
