[洛谷P2921][USACO08DEC]在农场万圣节Trick or Treat on the Farm

题目大意：给你一张有向图，每个点最多一条出边，问从每个开始，走多少步会到一个已经过的点

题解：$tarjan$缩点，然后建反图$DP$

卡点：无

C++ Code：

#include <cstdio>
#include <algorithm>
#define maxn 100010
int head[maxn], cnt;
struct Edge {
int to, nxt;
} e[maxn];
inline void addedge(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
}int n;
int nxt[maxn], ind[maxn], f[maxn];int DFN[maxn], low[maxn], idx;
int S[maxn], top, res[maxn], scc;
bool ins[maxn];
void tarjan(int u) {
DFN[u] = low[u] = ++idx;
ins[S[++top] = u] = true;
int v = nxt[u];
if (!DFN[v]) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if (ins[v]) low[u] = std::min(low[u], DFN[v]);
if (low[u] == DFN[u]) {
scc++;
do {
ins[v = S[top--]] = false;
f[res[v] = scc]++;
} while (v != u);
}
}int q[maxn], h, t;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", nxt + i);
for (int i = 1; i <= n; i++) if (!DFN[i]) tarjan(i);
for (int u = 1; u <= n; u++) {
int v = nxt[u];
if (res[u] != res[v]) {
addedge(res[v], res[u]);
ind[res[u]]++;
}
}
t = -1, h = 0;
for (int i = 1; i <= scc; i++) if (!ind[i]) q[++t] = i;
while (h <= t) {
int u = q[h++];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
f[v] += f[u];
if (!--ind[v]) q[++t] = v;
}
}
for (int i = 1; i <= n; i++) printf("%d\n", f[res[i]]);
return 0;
}