知识点

dfs树

对一个图运行 dfs 算法，每个点$u$的父亲定义为第一次遍历$u$时的前驱结点，若无则为根。
无向图的 dfs树 没有横叉边。
有向图的 dfs树 横叉边方向唯一，总是从后访问的点指向先访问的点。
dfs树详解

tarjan

点双

定义：

不存在割点的图。

性质：

两点一线型点双，较为特殊，以下在讨论特定性质时可能不纳入考虑范围。

1. 点双的dfs树上，根只有一个儿子，除叶子和根外每个点都有回边跨过。
   
2. 表述1：点双（两点一线型除外）中任意两点至少包含在一个简单环内。
   表述2：点双（两点一线型除外）中任意两点间都存在至少两条简单路径，并且这两条路径不经过相同的点。
   表述3：点双（两点一线型除外）中任意两条边至少包含在一个简单环内。
3. 对于点双中任意两点$u,v$，若点$p$在点双中，则一定存在$u-p-v$的简单路径；若点$p$不在点双中，则一定不存在$u-p-v$的简单路径。
   （对于点双中的任意一对点，连接它们的简单路径所经过点的并集一定就是这个点双本身。）
4. 对于点双中任意两点$u,v$，若边$p$在点双中，则一定存在$u-p-v$的简单路径。
5. 若点双中有奇环，由3.4.得任意两点间的简单路径有偶数长度和奇数长度的，所以点双里的所有边和点都在奇环上。
6. 一个有割点的无向图可以由若干个点双组成，点双间以割点相连接，两相邻的点双之间的公共点一定是唯一的，且一定是割点。
7. 无向图中的每个割点至少属于两个点双，其余点和每条边都只属于一个点双。
8. 点双连通分量一定是边双连通分量（两点一线型除外），反之不一定。

圆方树

圆方树是根据点双把无向图缩点所形成的树。
我们把每一个点双缩成一个 “方点”，把原有的点称作 “圆点”。然后我们把原图的边全部删除，让每个点向其所属的点双的 “方点” 连边。
显然，一个割点会向多个方点连边，而由此，除了根节点以外，所有的非割点都是叶子节点。 我们也知道，圆点和圆点之间不会互相连边，方点和方点之间也不会互相连边。

（第一个是原图，第三个是原图对应的圆方树）

应用：

• 处理有关简单路径的问题
• 处理有关图的连通性的问题
• %%%大佬的Blog

边双

定义：

不存在桥的图。

性质：

1. 边双的dfs树上，每条树边都有回边跨过。
2. 表述1：边双中任意一条边都包含在至少一个简单环中。
   表述2：边双中任意两点间都存在至少两条简单路径，并且这两条路径不经过相同的边。
3. 不是点双的边双可以由点双组成。
   
   （由两个点双组成的边双）
4. 在一个有割边的无向图中，把每一个边双缩成一个点，然后这些点之间由原来的割边相连形成了一棵树。
5. 无向图中两点一线型点双的边其实就是割边，割边不属于任何边双，而其它非割边的边都属于且仅属于一个边双。

小小总结：

点双和边双都是 由一些简单环组成的无向连通图，
不严谨地说，点双是"边的集合"，边双是"点的集合"。
图上的简单路径问题，一般用圆方树（点双）解决。

强连通分量

定义：

若有向图$G$满足：图中任意两点$u,v$间都存在从$u$到$v$的有向路径和从$v$到$u$的有向路径，则称$G$是一个强连通图。有向图的极大强连通子图，称为强连通分量。

性质：

1. 在强连通图中，每个点的入度和出度一定都不为0。
2. 把有向图中的每个强连通分量缩成一个点，将得到一个$DAG$(有向无环图)。

Kosaraju 算法

SAT & 2-SAT

入门讲解
入门讲解

题目

POJ2942 Knights of the Round Table

题意：判断每个点是否能在奇环内。

题解：若点在一个奇环内，则这个环一定在点所在的点双内，而点双中只要存在一个奇环，点双中的所有点都可以在奇环上。奇环的判断：二分图染色后，只要有一个点和它的相邻节点的颜色相同，就找到了奇环。

Code

AGC038D Unique Path

%%%zjr学长

摘自此Blog

XSY3273 graph

题意：有一个无向图，它没有重边和自环。现在有一些询问，形如“$u,v$之间是否存在一条长度为奇数的简单路径？” 这里简单路径定义为不经过重复的点的路径。

题解：首先建出dfs树，然后判断$u,v$间的树上路径长度是否为奇数
不是奇数的话考虑原图的圆方树，因为任意两点间的简单路径都可以拆分成经过的点双，所以就有以下结论：
对于树上距离为偶数的$u,v$，它们之间存在长度为奇数的简单路径当且仅当它们的树上路径经过了至少一条在奇环上的边
所以只需要求树上路径是否经过这样的边，每找到一个奇环，这个奇环所在的点双所包含的边都是满足要求的边，tarjan预处理即可

Code

HDU2767 Proving Equivalences

如果这个图本身就是强连通的，不用加任何边。
否则把每个强连通分量缩成一个点，得到一个$DAG$。记$in[i]$为点$i$的入度，$out[i]$为点$i$的出度，那么$DAG$上的点可以分为以下四类：

1. $in[i]>0,out[i]>0$
2. $in[i]=0,out[i]>0$
3. $in[i]>0,out[i]=0$
4. $in[i]=0,out[i]=0$

贪心策略：第3类点向第2,4类点连边，第4类点再向第2类点连边
所以令$DAG$变为强连通，加的最少边数为$max(入度为0的点数,出度为0的点数)$

POJ3177 Redundant Paths G

题解：
把边双缩成点。
$tarjan$缩点后图变成树，首先特判树中点数$n\le 2$的情况。
考虑$n>2$的情况，答案为⌊cntleaf+12⌋\lfloor\frac{cnt_{leaf}+1}{2}\rfloor⌊2cntleaf​+1​⌋。
构造具体方案时，以任意度大于$1$的点为根，只需要保证任意两个叶子连边后与根成环，
当奇数个叶子时，可以将一个叶子与根相连，又转换成了偶数叶子情况。

具体构造：
$tarjan$缩点后图变成树，选择度数大于$1$的点为根，按照$dfs$序存下所有叶子，$leaf[i]$表示按$dfs$序排序后的第$i$个叶子，共$g$个叶子。
将$leaf[i]$与leaf[i+⌊g2⌋]leaf[i+\lfloor\frac{g}{2}\rfloor]leaf[i+⌊2g​⌋]连边，(i≤⌊g+12⌋i\leq \lfloor\frac{g+1}{2}\rfloori≤⌊2g+1​⌋)。

构造方法证明：
见2020牛客多校第三场C

CF1000E We Need More Bosses

“必须经过的边”就是$s$到$t$路径上的割边，把无向图中的边双缩成点，得到一棵树，求树的直径即可。

Code

CF1137C Museums Tour

$d\le 50$

摘自此Blog

Code

CF1220E Tourism

在边双内走，一定能回到原点，故把边双缩成点。

然后就是树形DP：
$f[cur]$代表走到$cur$子树还能回的贡献，$g[cur]$代表走到$cur$子树回不来的贡献，题目所求即为$g[s]$。

先考虑$f$的转移， 如果子节点能回来：$f[cur]+=f[to]$
然后$g[cur]=max(g[to])+f[cur]$（走完所有可以返回的儿子再找个最大的不能返回的）

这样有一个问题，如果$f[cur]<g[cur]$，结点$cur$是否要返回
于是再：$g[cur]=max(g[cur],f[cur]-f[to]+g[to])$
摘自此Blog

Code

CF732F Tourist Reform

Blog

Code

POJ3694 Network

题意：在线查询一个无向图加入一条边后减少了多少条桥。
题解：先将所有的边双缩点，得到一颗树。初始时桥数即为树的边数，树边边权皆为1。
每次询问加入边$(x,y)$，设$c[i]$表示点$i$所在边双。
若$c[x]==c[y]$，无影响。
否则，减去的桥数为树上$c[x]$到$c[y]$的路径上边权的和，然后把该路径上树边的边权全部改为0。

[HNOI2012]矿场搭建

摘自此Blog