有向图Tarjan的题目

好吧$Tarjan$的题目实在有点多，所以有向图和无向图就分开吧，这里是有向图篇。

$B3609$ 模版题，不说了。

$P2863$ 求强连通分量时记录联通分量大小，最后数$size>1$的个数即可。

$P2341$ 先缩点，构建出$DAG$。如果出度为$0$的点只有一个的话，就输出这个点代表的强联通分量中的点的个数，否则输出$0$即可。

$P3387$ 先缩点，再用$topo$排序求出最长路即可。

$P3627$ 缩点时只用市中心作为出发点，这样就可以保证抢最多钱的方案一定从市中心出发。然后缩点，$topo$排序，最后只考虑有酒吧的联通分量所代表的点的$dp$值即可。

$P1407$ 这题当时卡了我好久。这题的做法是夫妻从男人往女人连，私奔的从女人往男人连，反过来也可以，看你的心情。然后缩点，如果一对夫妻在同一个强联通分量里，那么就$Unsafe$，否则就$Safe$。
那么为什么这么做是对的呢？首先如果一对夫妻$(Boy,Girl)$在一个强联通分量里，那么$Boy$可以到达$Girl$，$Girl$也可以到达$Boy$。那么一定有一个包含$Boy$和$Girl$的环。由于我们的建图，从$Boy$开始，一定是先走夫妻，再走私奔，先走夫妻，再走私奔……最后回到$Boy$。这样一定有一种替换方案。其次如果一对夫妻$(Boy,Girl)$不在一个强联通分量里，那么两人不能互相到达，那么这对夫妻肯定是安全的。
这也是为什么这道题不能用无向图的原因。其实这题是给无向图去定向的。如果是无向图，用边双做的话，那么就不一定是夫妻、私奔交替出现了，答案也就错了。

$P2272$ 这题还可以，显然原图的最大半联通子图是缩点后$DAG$上的一条链。于是在$DAG$上进行$topo$排序，用$(max,ways)$的$dp$即可。注意到建$DAG$那一步时，可能会有重边，而重边会干扰我们的$dp$。所以用$set$取出后，做$dp$才是正确的解法。

$P2515$ 这题直接写树形$dp$可以获得$40$分的好成绩。很显然原图是一棵以$0$为根的树加上一片基环树森林。于是对基环树森林进行缩点，然后把代表环的强联通分量向$0$连边，得到一棵新的树。对新树跑一遍树背包即可，复杂度是够的。

$P2746$ $P2812$ 首先先缩点。第$1$个问题的答案就是$DAG$上入度为$0$的点的个数。第$2$个问题的答案就是$DAG$上入度为$0$的点与出度为$0$的点个数的最大值。结论比较显然，考试时不要严格证明。注意，如果原图就是强联通图的话，第$2$个问题的答案就要为$0$。

$P4306$ 先缩点，然后问题就转化成了$DAG$上的连通性问题。我们想知道$DAG$上的两点是否联通，因为$n$有$2000$，就要使用$bitset$进行处理，答案用联通分量的$size$随便统计一下就行了，复杂度$O(n^3/w)$。

有向图$Tarjan$的题目到此结束！