记录编号 |
66818 |
评测结果 |
AAAAAAAATA |
题目名称 |
[USACO Dec08] 奶牛的糖果 |
最终得分 |
90 |
用户昵称 |
老师好~~~ |
是否通过 |
未通过 |
代码语言 |
C++ |
运行时间 |
2.467 s |
提交时间 |
2013-08-02 11:08:21 |
内存使用 |
4.52 MiB |
显示代码纯文本
#include<fstream>
using namespace std;
ifstream fin("treat.in");
ofstream fout("treat.out");
int c,cx,cd;
int a[100001],ans[100001],path[100001];
bool b[100001]={0};
void dfs(int x,int step)
{
if(b[x]==1)
{
c=1;//c表示是否在环中,cx记录环点,cd记录长度
cx=x;
cd=1;
int k=step;
while(path[k]!=x)
{
k--;
cd++;
}
ans[x]=cd;//寻找在环中的结点的长度
}
else
{
b[x]=1;
path[step+1]=x;
dfs(a[x],step+1);
if(x==cx)
c=0;
else
{
if(c==1)
ans[x]=cd;
else
ans[x]=++cd;
}
}//环外的结点的长度
}
int main()
{
int n,j,i;
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i];
for(i=1;i<=n;i++)
{
if(ans[i]==0)
{
for(j=1;j<=n;j++)
b[j]=0;
c=0;
dfs(i,0);
}
}
for(i=1;i<=n;i++)
fout<<ans[i]<<endl;
return 0;
}