题解 P2921 【[USACO08DEC]在农场万圣节Trick or Treat on the Farm】
pantw
2018-01-16 20:44:24
做法类似于NOIP2015 D1T2 message。
拓扑排序删链 → 对环上的点计算答案 → dfs计算其他点的答案。
环上的点答案都一样，可以一遍dfs跑出来；
其他点的答案在dfs返回的时候+1即可。
实现细节详见代码。
```cpp
#include <cstdio>
#define maxn 100010
int next[maxn], in[maxn], ans[maxn];
bool vis[maxn];
void del(int cur) {
vis[cur] = true;
in[next[cur]]--;
if(!in[next[cur]]) del(next[cur]);
}
int calccircle(int cur, int depth) {
ans[cur] = depth;
if(ans[next[cur]]) return depth;
else return ans[cur] = calccircle(next[cur], depth + 1);
}
int calc(int cur) {
if(ans[cur]) return ans[cur];
else return ans[cur] = calc(next[cur]) + 1;
}
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", next + i), in[next[i]]++;
for(int i = 1; i <= n; i++) if(!in[i] && !vis[i]) del(i);
for(int i = 1; i <= n; i++) if(in[i] && !ans[i]) calccircle(i, 1);
for(int i = 1; i <= n; i++) if(!in[i] && !ans[i]) calc(i);
for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
}
```