题目描述
每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的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.
代码
tarjan算法缩点之后就是一个DAG，之后拓扑排序一下就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100000+5; inline void read(int &x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n,tot,top,idx,cnt; int head[maxn],w[maxn],nxt[maxn],dis[maxn],du[maxn]; int dfn[maxn],low[maxn],sta[maxn],B[maxn]; bool instack[maxn]; struct node{ int next,to; }e[maxn]; inline void ins(int from,int to){ e[++tot].next=head[from]; e[tot].to=to; head[from]=tot; } void tarjan(int x){ dfn[x]=low[x]=++idx; sta[++top]=x; instack[x]=true; for(int i=head[x];i;i=e[i].next) if(!dfn[e[i].to]){ tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); }else if(instack[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(dfn[x]==low[x]){ int y; ++cnt; do{ y=sta[top--]; instack[y]=false; B[y]=cnt; ++w[cnt]; }while(x!=y); } } void dfs(int x){ if(dis[x]) return; dis[x]=w[x]; for(int i=head[x];i;i=e[i].next) dfs(e[i].to),dis[x]+=dis[e[i].to]; } int main(){ read(n); for(int i=1;i<=n;++i){ read(nxt[i]); ins(i,nxt[i]); } for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); tot=0; memset(head,0,sizeof(head)); for(int i=1;i<=n;++i) if(B[i]!=B[nxt[i]]) ins(B[i],B[nxt[i]]),du[B[nxt[i]]]++; for(int i=1;i<=n;++i) if(!du[i]) dfs(i); for(int i=1;i<=n;++i) printf("%d ",dis[B[i]]); return 0; }