- 信息传递
- 2016-11-14 20:56:04 @
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=200010;
int next[MAX],pre[MAX]={0},visit[MAX]={0};
int empty(int x)//清边
{
int y,z;
while(pre[x]==0)
{
visit[x]=1;
pre[next[x]]--;
y=next[x];
next[x]=0;
x=y;
}
return 0;
}
int dfs(int x)//找环
{
int y,z=0;
while(next[x]!=0)
{
z++;
y=next[x];
next[x]=0;
x=y;
}
return z;
}
int main()
{
int i,j,k,l,m,n,ans=0x7ffffff;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&next[i]);
pre[next[i]]++;
}
for(int i=1;i<=n;i++)
{
if((pre[i]==0)&&(visit[i]!=1))
{
empty(i);
}
}
/* for(int i=1;i<=n;i++)
{
cout<<next[i]<<" "<<pre[i]<<" "<<visit[i]<<endl;
}*/
for(int i=1;i<=n;i++)
{
if(next[i]!=0)
{
ans=min(ans,dfs(i));
}
}
cout<<ans;
return 0;
}
2 条评论
-
Stuart3 LV 8 @ 2016-11-14 20:59:51
洛谷上就过了啊。。
-
2016-11-14 20:57:58@
因为你出错了
- 1
信息
- ID
- 1979
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 4096
- 已通过
- 980
- 通过率
- 24%
- 被复制
- 9
- 上传者