题目描述

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N个牛棚里转 悠，来采集糖果.她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果.

农场不大，所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛 棚”.牛棚i的后继牛棚是next_i 他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去， 就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段，来节约他的糖果.

第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．

输入输出格式

输入格式：

• Line 1: A single integer: N

• Lines 2..N+1: Line i+1 contains a single integer: next_i

输出格式：

• Lines 1..N: Line i contains a single integer that is the total number of unique stalls visited by cow i before she returns to a stall she has previously visited.

输入输出样例

输入样例#1：

4

1

3

2

3

输出样例#1：

1

2

2

3

说明

Four stalls.

• Stall 1 directs the cow back to stall 1.

• Stall 2 directs the cow to stall 3

• Stall 3 directs the cow to stall 2

• Stall 4 directs the cow to stall 3

Cow 1: Start at 1, next is 1. Total stalls visited: 1.

Cow 2: Start at 2, next is 3, next is 2. Total stalls visited: 2. Cow 3: Start at 3, next is 2, next is 3. Total stalls visited: 2. Cow 4: Start at 4, next is 3, next is 2, next is 3. Total stalls visited: 3.

Solution

这道题思路不是很难,不过我代码能力太弱了,打了三遍才过...

思路如下:

1) 先把不是环的处理出来,此步可以通过拓扑排序实现

2) 把环都先处理完,直接在深搜的时候判断是否走过即可

3) 最后把所有的都处理完,用了一点点DP的思想.

转移方程如下:

\[f[now]=f[next]+1 \]

然后最后输出即可.

代码

#include 
    
     using namespace std;const int maxn=100008;int ru[maxn],to[maxn];int f[maxn],n,v[maxn];void pre(int x) {    v[x] = true;    ru[to[x]]--;    if(!ru[to[x]]) pre(to[x]);}int dfs1(int x, int now) {    f[x] = now;    if(f[to[x]])return now;    return f[x]=dfs1(to[x], now+1);}int work(int x) {    if(f[x]) return f[x];    return f[x]=work(to[x])+1;}int main() {    ios::sync_with_stdio(false);    cin>>n;    memset(f,0,sizeof(f));    for(int i=1;i<=n;i++) cin>>to[i], ru[to[i]]++;    for(int i=1;i<=n;i++)if(!ru[i]&&!v[i])pre(i);    for(int i=1;i<=n;i++)if(ru[i]&&f[i]==0)dfs1(i, 1);    for(int i=1;i<=n;i++)if(!ru[i]&&f[i]==0)work(i);    for(int i=1;i<=n;i++)cout<
     
      <