无向图Tarjan的题目

这里是无向图篇。

$P3388$ 割点模版题。

$P3469$ 在求割点的时候，遇到$dfn_u<=low_v$时，对节点$u$的答案进行计算即可，注意细节。

$P3225$ 这题用割点和点双做最好(别像$captainOI$一样用圆方树)。首先先求出割点，特判掉$N=1$的情况。若原图没有割点，则就要任意选取$2$个点。若原图有割点，则只有含$1$个割点的点双需要安装出口，且只能在非割点处。这样做显然是对的。

$P1656$ 割边模版题。

$P8435$ 点双联通分量模版题，注意处理孤点和自环的情况。

$P8436$ 边双联通分量模版题。

$P5058$ 这个题有$2$种做法。
第$1$种做法是用割点做。显然问题的答案一定是割点。为了方便，我们可以以$a$为根，向下进行$Tarjan$，来求割点。显然，$u$满足要求的充分必要条件是存在子树$v$，使得$u$会把$a$和$v$割开，且$b$在$v$的子树中。那么只剩一个问题，怎么判断$b$是否在$v$的子树内，答案就是在回溯到$(u,v)$时，看$dfn_v<=dfn_b$是否成立。得益于$dfn$用的是堆空间，我们这样做肯定是对的。这种做法比较容易写，但是比较难想。
第$2$种做法是大材小用地使用圆方树。建出圆方树，看$(a,b)$间的圆点编号最小的是谁就行了。这种做法好想也不难写。
注意在统计答案是不要把$a$和$b$也统计上！

$P8867$ 这题真的折磨了我好久，堪称我最喜欢的$NOIP$题。首先，根据大教授的提示，我们进行边双联通分量缩点。设$u$号边双内有$a_u$个点，$b_u$条边。设$f_{u,0/1/2}$表示考虑到以$u$为根的子树，没造军营/造了军营且能通到$u$/造了军营且通不到$u$的方案数。那么$f_{u,0}=2^b \times ∏(f_{v,0} \times 2)$，$f_{u,1}=2^b \times (2^a \times ∏(f_{v,0} \times 2 + f_{v,1}) - ∏(f_{v,0} \times 2))$，$f_{u,2}=2^b \times \sum_{v \in son_u}((f_{v,1}+f_{v,2}\times 2)\times ∏{w \in son_u,w!=v}(f \times 2))$。对于$∏{w \in son_u,w!=v}(f \times 2))$的处理，可以用总积乘逆元的方式处理。因此，总复杂度为$O(nlogp)$。

接下来看几道$POJ$的综合题。

$P6066$ $POJ2230$ 好吧我不知道为什么这题会在$Tarjan$这一章里。边与其反向边的$and$值要为$1$。从$1$开始$dfs$，树边就按$dfs$的走法，遇到返祖边时，请一定走$und$ $mod$ $2==0$的，走出去后立马回来，要不然会出事。

$POJ3694$ 好吧我不知道为什么这题会在$Tarjan$这一章里。先对原图建出一棵$dfs$生成树，显然有$n-1$条桥。然后对非树边和询问的处理都是一样的，都是利用并查集的合并性，把$x-lca(x,y)-y$的路径缩成一个点，每调用一次$merge$函数，就把桥的数量减$1$。这样就可以动态维护桥的数量了。

$POJ2942$ 这题才是$Tarjan$题。首先把有仇变成没仇，再去连边。然后求出该图的点双。显然的，桌子上的人一定在同一个点双里，且一定是那个点双里的奇环。所以我们可以对原图进行黑白染色，如果一条边的两端属于同一个点双，那么这个点双里的所有点都可行，否则这些点不一定可行。求两点的公共点双可以用圆方树，复杂度$O(n^2)$。

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