[BZOJ1589] [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果（tarjan缩点 + 记忆化搜索）

传送门

先用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; }

　　

上一篇：[BZOJ4779] [Usaco2017 Open]Bovine Genomics（hash + 二分）

下一篇：[BZOJ1594] [Usaco2008 Jan]猜数游戏（二分 + 并查集）

---

记忆化搜索 tarjan SCC