题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。
由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。
在*停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。
（翻译来自洛谷）
分析
比较容易可以想到，如果一个奶牛位于一个环中，那么它的答案就是这个环的大小。
如果一个奶牛不在一个环中，那么答案就是到它最近的环的距离再加上环的大小。
代码
#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define N 100005
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
struct edge {
int to, nt;
}E[N];
int H[N], dfn[N], vis[N], S[N], nxt[N], belong[N], low[N], ans[N], sum[N];
int scc, cnt, dfn_tot, top, n;
void add_edge(int u, int v) {
E[++ cnt] = (edge){v, H[u]};
H[u] = cnt;
}
void tarjan(int u) {
vis[u] = 1;
low[u] = dfn[u] = ++ dfn_tot;
S[top ++] = u;
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v]) low[u] = min(low[u], low[v]);
}
int j;
if (dfn[u] == low[u]) {
scc ++;
do {
j = S[-- top];
belong[j] = scc;
vis[j] = 0;
} while (u != j);
}
}
void dfs(int u, int nt, int dis) {
if (ans[nt] != 0) {
ans[u] = ans[nt] + dis;
return;
}
else dfs(u, nxt[nt], dis + 1);
}
int main() {
read(n);
for (int i = 1; i <= n; i ++) {
read(nxt[i]);
add_edge(i, nxt[i]);
if (nxt[i] == i) ans[i] = 1;
}
for (int i = 1; i <= n; i ++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i ++) sum[belong[i]] ++;
for (int i = 1; i <= n; i ++)
if (sum[belong[i]] != 1) ans[i] = sum[belong[i]];
for (int i = 1; i <= n; i ++)
if (ans[i] == 0) dfs(i, nxt[i], 1);
for (int i = 1; i <= n; i ++) printf("%d\n", ans[i]);
return 0;
}