Strongly connected component

USACO08DEC

Title Description

Every year in Wisconsin the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N (1 <= N <= 100,000) stalls conveniently numbered 1..N.

Because the barn is not so large, FJ makes sure the cows extend their fun by specifying a traversal route the cows must follow. To implement this scheme for traveling back and forth through the barn, FJ has posted a 'next stall number' next_i (1 <= next_i <= N) on stall i that tells the cows which stall to visit next; the cows thus might travel the length of the barn many times in order to collect their candy.

FJ mandates that cow i should start collecting candy at stall i. A cow stops her candy collection if she arrives back at any stall she has already visited.

Calculate the number of unique stalls each cow visits before being forced to stop her candy collection.

POINTS: 100

Input format

* Line 1: A single integer: N

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

Output format

* 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.

Title Translation

Title Description

Every year, , In Wisconsin , The cows put on their clothes , Collecting Farmer John is in N(1<=N<=100,000) Candy left in a cowshed compartment , To celebrate the fall of Halloween in the United States .

Because the cowshed is not too big ,FJ Ensure the fun of cows by specifying the crossing route that cows must follow . In order to realize the plan of making cows shuttle back and forth in the cowshed ,FJ In the i There is a posted on compartment No “ Next compartment ”Next_i(1<=Next_i<=N), Tell the cow to go to the next compartment ; such , To collect their candy , Cows will shuttle back and forth in the barn .

FJ Order cows i It should be from i Compartment No. 1 starts collecting candy . If a cow goes back to a cubicle she has been to , She will stop collecting candy .

Before being forced to stop collecting candy , Calculate the number of compartments each cow will go to （ Including the starting point ）.

Input format

The first 1 That's ok Integers n.

The first 2 Row to n+1 That's ok Each line contains an integer next_i .

Output format

n That's ok , The first i Line contains an integer , It means the first one i The number of compartments a cow will go to .

Sample explanation

Yes 4 Compartments

cubicle 1 Request cattle to the compartment 1

cubicle 2 Request cattle to the compartment 3

cubicle 3 Request cattle to the compartment 2

cubicle 4 Request cattle to the compartment 3

cattle 1, from 1 Departure from compartment No , A total of access 1 Compartments ;

cattle 2, from 2 Departure from compartment No , Then go to compartment three , And then to 2 Compartment No , End , A total of access 2 Compartments ;

cattle 3, from 3 Departure from compartment No , And then to 2 Compartment No , And then to 3 Compartment No , End , A total of access 2 Compartments ;

cattle 4, from 4 Departure from compartment No , And then to 3 Compartment No , And then to 2 Compartment No , And then to 3 Compartment No , End , A total of access 3 Compartments .

Translation provider ： Eat grapes and spit sugar

I/o sample

Input #1 Copy

4 
1 
3 
2 
3 

Output #1 Copy

1 
2 
2 
3 

explain / Tips

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.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int nexts[N],ans[N];
vector<int>G[N];
int n;
int sum,color[N],low[N],ins[N],dfn[N],col;
int Lemon[N];
stack<int>s;
void tarjan(int x)
{
    sum++;
    dfn[x]=low[x]=sum;
    s.push(x);
    ins[x]=1;
    for(int i=0; i<G[x].size(); i++)
    {
        if(ins[G[x][i]]==0)
        {
            tarjan(G[x][i]);
            low[x]=min(low[x],low[G[x][i]]);
        }
        else if(ins[G[x][i]]==1)
            low[x]=min(low[x],dfn[G[x][i]]);
    }
    if(dfn[x]==low[x])
    {
        col++;
        int node;
        do
        {
            node=s.top();
            s.pop();
            color[node]=col;
            ins[node]=-1;
        }
        while(node!=x);
    }
    return ;
}
void search(int root,int x,int step)
{
    if(ans[x]!=0)
    {
        ans[root]=ans[x]+step;
        return ;
    }
    else search(root,nexts[x],step+1);
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>nexts[i];
        G[i].push_back(nexts[i]);
        if(nexts[i]==i)ans[i]=1;
    }
    for(int i=1; i<=n; i++)
    {
        if(ins[i]==0)
            tarjan(i);
    }
    for(int i=1; i<=n; i++)
    {
        Lemon[color[i]]++;// Record the size of the ring 
    }
    for(int i=1; i<=n; i++)
        if(Lemon[color[i]]!=1) ans[i]=Lemon[color[i]];// Deal with points in the ring 
    for(int i=1; i<=n; i++)
        if(ans[i]==0) search(i,nexts[i],1);// Deal with points outside the ring .
    for(int i=1; i<=n; i++)
        cout<<ans[i]<<endl;
    return 0;
}