传送门
先用tarjan缩点，再记忆话搜索一下
#include <stack> #include <cstdio> #include <cstring> #include <iostream> #define N 100001 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, cnt, rp, tot, cnt1; int head1[N], to1[N], next1[N], head[N], to[N], next[N], dfn[N], low[N], belong[N], ans[N], a[N]; bool ins[N]; std::stack <int> s; inline int read() inline void add(int x, int y) inline void add1(int x, int y) inline void tarjan(int u) else if(ins[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]) while(u ^ v); } } inline int dfs(int u) return ans[u] += a[u]; } int main() for(i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(i = 1; i <= n; i++) a[belong[i]]++; for(u = 1; u <= n; u++) for(i = head[u]; i ^ 1; i = next[i]) for(i = 1; i <= n; i++) printf("%d\n", dfs(belong[i])); return 0; }
上一篇：[BZOJ1663] [Usaco2006 Open]赶集（spfa最长路）
下一篇：[POJ2778]DNA Sequence（AC自动机 + DP + 矩阵优化）
tarjan SCC 记忆化搜索
