[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

[POJ3728]The merchant（tanrjan_lca + DP）传送门

比着题解写还错。。。
查了两个小时没查出来，心态爆炸啊
以后再查

——代码（WA）


1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #de

[luoguP2680] 运输计划（lca + 二分 + 差分）传送门

暴力做法 50 ~ 60
枚举删边，求最大路径长度的最小值。
其中最大路径长度运用到了lca

我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。
先把

[luoguP2863] [USACO06JAN]牛的舞会The Cow Prom（Tarjan）传送门

有向图，找点数大于1的强连通分量个数

——代码


1 #include <stack>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5
6 const int MA

[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）传送门

题意

N个点M条边的有向图
每个点有点权
从某一个结点出发
问能获得的最大点权和
一个点的点权最多被计算一次
N<=500000 M<=500000

思路
先tarjan缩点，然后就形成

[HDU3062]Party（2-sat）传送门
2sat问题，只需要判断yes或no
所以可以直接连边，缩点，判断同一组的是否在同一个块中。


1 #include <cstdio>
2 #include <stack>
3 #include <cstring>
4 #includ

[HAOI2006]受欢迎的牛（tarjan缩点）洛谷传送门
直接tarjan求scc，然后统计出度为0的缩点，如果多余1个就输出0，只有一个就输出这个缩点里的点。
——代码


1 #include <cstdio>
2 #include <cstring>
3 #inclu

【割点】【割边】tarjan洛谷割点模板题——传送门

割边：在连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。
割点：在连通图中，删除了连通图的某个点以及与这个点相连的边后

lca最近公共祖先（模板）洛谷上的lca模板题——传送门
1.tarjan求lca
学了求lca的tarjan算法（离线），在洛谷上做模板题，结果后三个点超时。
又把询问改成链式前向星，才ok。
这个博客，tarjan分析的很详细。

【模板】Tarjan求强连通分量有人说这篇博客不是很友好，所以我加了点解释，感觉是不是友好多了？
dfn[u]表示节点u在dfs时被访问的次序。
low[u]表示节点u能够追溯到的最远的祖先的dfn。
ins[u]表示节点u是