连通分量

连通分量：需要保存边用dfs，不需要保存边用并查集

二分图

二分图：非连通图是二分图当且仅当每个连通分量都是二分图。
一个连通图是二分图，当且仅当它可以二染色。
一个连通图是二分图，当且仅当它不含奇数环，所谓奇数环，即环上的点（或边）个数为奇数。

反证法证明一个二分图当且仅当不含奇数环。

证明：
假设二分图含有奇数环，设顶点编号分别为x1,x2,x3…,x2k−1$x_1,x_2,x_3\dots ,x_{2k-1}$，其中k∈N+$k\in N^{+}$，根据假设有x1$x_1$与x2k−1$x_{2k-1}$相连。
不失一般性，假设x1$x_1$属于X$X$集合，那么x2$x_2$属于Y$Y$集合，以此类推x3$x_3$属于X$X$集合，x4$x_4$属于Y$Y$集合。
则有x2p$x_{2p}$属于X$X$集合，x2p−1$x_{2p-1}$属于Y$Y$集合，其中p∈N+$p\in N^{+}$。
那么x1$x_1$与x2k−1$x_{2k-1}$都属于X$X$集合，但是他们之间仍旧有连边，这不符合二分图的定义。故假设不成立。

割顶

割顶：对于无向图G​$G$，若删除某个点v​$v$后，其连通分量的个数增加，那么点v​$v$称作图G​$G$的割顶。

求法：dfs算法，线性时间复杂度。

对于一张图，使用dfs不重复的遍历每一个节点，可以得到一颗dfs树

如图，如果不区分上图中的红色和黑色边，并且忽略掉图中边的方向，可以看做是一个无向图。

如果区分红边和黑边，并且不忽略方向，对于上图有如下的解释：

1. 从顶点编号为1开始遍历，编号的顺序即为访问到的顺序。
2. 箭头的方向表示遍历的方向。
3. 黑色边表示父子边，具体而言对于<u,v>$<u,v>$表示从u$u$遍历到v$v$。红色边表示返祖边。因为其祖先已经访问过，根据刚才dfs的定义，要不重复的遍历每一个节点，所以对于祖先我们不访问。

算法实现借助于一下几个数组：

1. dfn[v]$dfn[v]$：表示对于节点v$v$的时间戳
2. low[v]$low[v]$：表示能节点v$v$通过其自身的返祖边，能够返回到祖先最早的时间戳。（注意在dfs的时候，一路都会更新自身节点的low)

算法借助于下面的几个定理：

1. 对于一条返祖边(u,v)$(u,v)$，要么u$u$是v$v$的祖先，要么u$u$是v$v$的后代。（注意是无向边）。
2. 对于一条父子边(u,v)$(u,v)$，且dfn[u]>1$dfn[u]>1$，low[v]≥dfn[u]$low[v]\ge dfn[u]$，那么u$u$是割顶。通俗来说，若非根节点u$u$是割顶，存在其子节点v$v$，使得v$v$及其所有后代都没有返祖边连接到u$u$的祖先（连接到u$u$不算）。
3. 对于节点u$u$，且dfn[u]=1$dfn[u]=1$时，u$u$是割顶的充要条件为，存在至少2条从u$u$出发的父子边。

定理1显然可得。

定理2的证明如下。
证明： 考虑u$u$的一个子节点v$v$，如果v$v$或者其所有后代中，有一个点连接到u$u$的祖先，那么去掉u$u$之后，在以v$v$为根的子树上还可以通过这条连接到u$u$的祖先的返祖边连接到u$u$的祖先，保持和u$u$祖先的连通性。反之，若去掉u$u$，则以v$v$为根的子树就与u$u$的祖先以及u$u$除去v$v$的其他子树断开了，这样连通分量数目增加。

下面再说明为何文字说明等价于low[v]≥dfn[u]$low[v]\ge dfn[u]$。
首先可以明确的一点是，因为v$v$是u$u$的子树，所以dfn[u]<dfn[v]$dfn[u]<dfn[v]$。若以v$v$为根的子树中不包含连接到u$u$的祖先的返祖边，那么以v$v$为子树的所有节点中，都满足low[x]≥dfn[u]$low[x]\ge dfn[u]$ （其中x$x$表示以v$v$为根的子树中的节点，包括v$v$），由于v∈x$v\in x$，那么就会有low[v]≥dfn[u]$low[v]\ge dfn[u]$，证毕。

特别说明一下，low[x]=dfn[u]$low[x]=dfn[u]$时，当且仅当以v$v$为根的子树中存在一节点，其返祖边连接至u$u$，且不存在连接至u$u$的任何祖先的返祖边。

此外，dfn[u]>1$dfn[u]>1$表明节点u$u$不是dfs遍历的时候的第一个节点，对于dfs树根节点是否是割点的判定，依赖于定理3。

定理3直观理解也很显然，考虑一棵树，他的根节点有多个子节点（大于等于2个），我们直接把根节点拿走，子树的数目必然增多。定理3和道理一样。

割边（桥）

割边：对于无向图G$G$，若删除某条边(u,v)$(u,v)$后，其连通分量的个数增加，那么点称作边(u,v)$(u,v)$图G$G$的割边。

对于割边，我们同样的使用dfs进行求解，他的判定条件为，若low[v]>dfn[u]$low[v]>dfn[u]$，当前边则为割边。

双连通分量

双连通图（块、2-连通图）：没有割顶的图称为双连通图。也可以理解为，对于一个双连通图，其中任意两点存在2条不经过重复点的路径。

如图，每个蓝色线圈即为一个块，可以看到块中没有割点。每个块由割边相连。对于每一个块，可以缩点形成一个树。

对于块，同样适用dfs方法进行求解。当其遍历完所有边之后，若low[u]==dfs[u]$low[u]==dfs[u]$，那么此点之下的所有点（对应dfs树），均在一个块内。为了求解出这些点，在dfs的时候利用栈暂存所有的边上的点，当找到一个块的时候，对其中的点弹栈，加入到对应的块内。

点双连通分量：删除图中所有的割顶之后，每个连通分量对应一个点双连通分量。

边双连通分量：删除图中所有的割边之后，每个连通分量对应一个边双连通分量。

点双连通分量在求解过程之中，用栈保存其中的边或点（取决于题目），然后在找到一个割顶之后，对栈中的进行弹栈，依次加入到对应的连通分量中。

边双连通分量，可以分两次dfs求解。第一次dfs求解出所有的割边。由于边双连通分量是由边连接两个顶点，所以说各个连通分量之间没有公共的顶点，根据这个，我们可以在第二次dfs的时候，不经过割边即可。

强连通分量

有向图的每一个强连通分量，都是原图的一个极大连通子图。所谓强连通分量，即对于强连通分量重的每一对顶点u,v$u,v$，存在两组不相同的从u$u$到v$v$和从v$v$到u$u$的路径序列。

强连通分量的求解，使用tarjan算法。tarjan算法借助于dfs。回忆刚才的dfs树：对于无向图来说，只有2种边，父子边和返祖边。但是对于有向图来说，有4种边，分别是：父子边，返祖边，横叉边，前向边。

看如下的dfs树。

（图片来自 Tarjan算法寻找有向图的强连通分量 – Miskcoo’s Space ）

横叉边：如图中的从6−4$6-4$短虚线的边，就是横叉边。可以看到是从dfn$dfn$较大的节点想dfn$dfn$较小的节点发出的边。也就是从当前节点向之前遍历过的子树节点出发的边，并且他们之间不存在儿子和祖先之间的关系。

前向边：图中并没有。假设图中有一条从1−6$1-6$的边，那么这条边就是前向边。因为他是从一个祖先节点想其儿子节点出发的一条有向边。根据dfs的性质，其儿子节点一定比祖先节点先完成比遍历。所以这样的边是无法更新新信息的。并且根据刚才的经验，在运行算法的时候，先判断下面要访问的节点是否有时间戳，如果没有（即没有访问过）或者是时间戳比当且节点的时间戳要小（说明是返祖边），再进行访问。所以前向边是无法进行更新的。

在求解强连通分量的时候，借助一个栈S来完成。栈中保存当前遍历经过的节点，在栈中的节点，表示当前还没有分配到某个强连通分量中。

在更新low[u]$low[u]$的时候，和之前的情况十分类似，分为两种情况：

1. 通过父子边(u,v)$(u,v)$从u$u$走到节点v$v$。那么需要更新u$u$的low$low$值，low[u]=min(low[u],low[v])$low[u]=min(low[u],low[v])$。
2. 通过返祖边或者横叉边(u,v)$(u,v)$从u$u$走到节点v$v$，也需要更新u$u$的low$low$值，但此时注意，需要判断v$v$是否在栈中（或者判断是否已经分配到某个强连通分量中，根据标号判断也可以）。因为若v$v$已经分配到某个强连通分量中，是不能通过这条边在回到u$u$的，所以这样的更新是不合法的。若v$v$在栈中（未被分配强连通分量），那么就有low[u]=min(low[u],dfn[v])$low[u]=min(low[u],dfn[v])$。

当遍历完某个节点时（遍历完指的是遍历完其所有的边），若low[u]==dfn[u]$low[u]==dfn[u]$，那么栈中从栈顶到当前节点均属于一个强连通分量。

下面来证明这个结论。
考虑有向连通图的dfs树。假设u$u$是dfs中某个强连通分量的第一个顶点（强连通分量的根），那么这个强连通分量中的某个顶点，一定在以u$u$为根的子树中。若某个节点v$v$在这个强连通分量中，但是不在以u$u$为根的子树中，那么他一定通过某条返祖边或者横叉边离开子树，这样的边一定连接一个访问过的点，这就和u$u$是第一个顶点相矛盾。

而上述文字说明，可以抽象成low[u]==dfn[u]$low[u]==dfn[u]$。