题目描述

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

输入格式

第1行 整数n。

第2行到n+1行 每行包含一个整数 next_i 。

输出格式

n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

样例解释

有4个隔间

隔间1要求牛到隔间1

隔间2要求牛到隔间3

隔间3要求牛到隔间2

隔间4要求牛到隔间3

牛1，从1号隔间出发，总共访问1个隔间；

牛2，从2号隔间出发，然后到三号隔间，然后到2号隔间，终止，总共访问2个隔间；

牛3，从3号隔间出发，然后到2号隔间，然后到3号隔间，终止，总共访问2个隔间；

牛4，从4号隔间出发，然后到3号隔间，然后到2号隔间，然后到3号隔间，终止，总共访问3个隔间。

翻译提供者：吃葡萄吐糖

输入输出样例

输入 #1 <button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" style="border&#45;color&#58; &#35;3498db&#59; color&#58; &#35;3498db&#59; user&#45;select&#58; auto&#59;" type="button"> 复制 </button> 
4 
1 
3 
2 
3
输出 #1 <button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" style="border&#45;color&#58; &#35;3498db&#59; color&#58; &#35;3498db&#59; user&#45;select&#58; auto&#59;" type="button"> 复制 </button> 
1 
2 
2 
3 


思路
　　显然要想回到本身房间需要经历一个环的过程。
　　对于每个起点来说，这个点要么在环上，要么可以通过一条链到达一个环然后再转回来。
　　可以用染色法对于每个强连通分量染色。
　　如果一个点在一个环里，它能得到的糖果数量就是环的大小。
　　如果不在环里，就dfs循着邻边直到找到环为止，它所得到的糖果数就是这条链（起点到环上一点的父亲节点）长+环的大小。
CODE
  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 1e5 + 7;
  7 
  8 int head[maxn], dfn[maxn], low[maxn], st[maxn];
  9 int cnt = 0, tot = 0, tim = 0, top = 1, n, cl = 0;
 10 int vis[maxn];
 11 int color[maxn];
 12 int ans[maxn];
 13 int nxt[maxn];
 14 int circle_size[maxn];
 15 
 16 /*
 17 head[],结构体edge:存边
 18 
 19 dfn[],low[]:tarjan中数组
 20 
 21 st[]:模拟栈
 22 
 23 out[]:出边
 24 
 25 sd[]:强连通分量存储
 26 
 27 dq[]:统计答案
 28 */
 29 
 30 template<class T>inline void read(T &res)
 31 {
 32     char c;T flag=1;
 33     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 34     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 35 }
 36 
 37 struct Edge{
 38     int nxt, to;
 39 }edge[maxn * 2];
 40 
 41 inline void BuildGraph(int from, int to)
 42 {
 43     cnt++;
 44     edge[cnt].to = to;
 45     edge[cnt].nxt = head[from];
 46     head[from] = cnt;
 47 }
 48 
 49 void tarjan(int x)
 50 {
 51     tim++;
 52     dfn[x] = low[x] = tim;
 53     st[top] = x;
 54     top++;
 55     vis[x] = 1;
 56     for(int i = head[x] ; i != 0; i = edge[i].nxt)
 57     {
 58         int u = edge[i].to;
 59         if(vis[u] == 0)
 60         {
 61             tarjan(u);
 62             low[x]=min(low[x],low[u]);
 63         }
 64         else if(vis[u] == 1)
 65                 low[x]=min(low[x],dfn[u]);
 66     }
 67     if(dfn[x] == low[x])
 68     {
 69         cl++;
 70         do
 71         {
 72             top--;
 73             color[st[top]] = cl;
 74             vis[st[top]] = -1;
 75         }while( st[top] != x );
 76     }
 77     return ;
 78 }
 79 
 80 void dfs(int u, int x, int step) {
 81     if(ans[x] != 0) {
 82         ans[u] = ans[x] + step;
 83         return ;
 84     }
 85     else dfs(u, nxt[x], step+1);
 86 }
 87 
 88 int main()
 89 {
 90     scanf("%d",&n);
 91     for ( int i = 1; i <= n; ++i ) {
 92         scanf("%d",&nxt[i]);
 93         BuildGraph(i, nxt[i]);
 94         if(i == nxt[i]) {
 95             ans[i] = 1;
 96         }
 97     }
 98     for ( int i = 1; i <= n; ++i ) {
 99         if( !vis[i] ) {
100             tarjan(i);
101         }
102     }
103     for ( int i = 1; i <= n; ++i) {
104         circle_size[color[i]]++;
105     }
106     for ( int i = 1; i <= n; ++i) {
107         if(circle_size[color[i]]  != 1) {
108             ans[i] = circle_size[color[i]];     
109         }
110     }
111     for ( int i = 1; i <= n; ++i) {
112         if(ans[i] == 0) {
113             dfs(i, nxt[i], 1);
114         }
115     }
116     for ( int i = 1; i <= n; ++i) {
117         printf("%d\n",ans[i]);
118     }
119     return 0;
120 }
View Code