强连通分量
Tarjan
抽象难懂的算法
第一次接触链式前向星，本算法储存方式为链式前向星，用vector不香吗
这个算法很多什么low啊，dfn啊，把你搞得很晕……
其实整个算法就是基于DFS然后再加上玄学打标记搞定的。
这里只介绍Tarjan求割点 （因为其他我不会。
前置知识
割点
通俗的讲，就是一个图只要把这个点割了，就不连通了。
时间戳
在进行DFS的时候对每个点编号的方式，就是dfs第几个遍历到的。
搜索树
用DFS在一个 \(n\) 的图中构建一个 \(n-1\) 的数，感觉跟生成树比较像，但是是用DFS构造的
追溯值：low
low值得定义
书面定义：
设以x为根的搜索树子树为subtree(x),low(x)为x以下结点的dfn的最小值
- sub（x）中的结点
- 通过一条不是搜索树中的边到达一个sub(x)的点
很晕对吧，我也不懂（copy别人的。
于是我就用我理解的语言来讲解
这里就盗用OI wiki中的图片来讲解
我认为这个就是tarjan中令人难懂的一个点。
假设，我们已经对dfn进行了初始化。每个点上的值就是其dfn的值。图中黑色的边就是树边，也就是一个dfs生成树中的边。
而有一条红色的边，他不是树边，它却指向了一个dfn值比他小的边，也就是直接指向了自己某个祖宗。所以这个边就叫做返祖边。
如果此时还有一条返祖边（7，8）。（如图所示）：
结论：那么对于结点7他的low值就是1。
为什么呢？
因为有（7，1）和（7，8）这两条返祖边使得结点7连向了结点1和结点8，因为 \(1<8\) 所以 \(low_6\) 为 \(1\)。
接下来，我们考虑如何计算low值
初始化：很容易想到 \(low_i\) = \(dfn_i\)。因为连到自己也是可以的嘛。
如果对于 \(x\),有一个 (\(x\),\(y\))的连边。
-
如果y是在搜索树中x的子树内,那么 \(low_x\) = \(min(low_x,low_y)\)。因为如果它的子树有一条连到更小的点的返祖边，那么肯定也得算上它自己
-
如果(\(x,y\))不是一条树边（就例如7和9吧）。那么只能用 \(dfn_y\) 来更新 \(low_x\) ，因为他们又不是一个搜索树中，所以最多就只能说是 \(x\) 有连了一条边到了 \(y\) 。那么最多也就是更新一下到达的点中最小的值而已（就是low）。再根据定义，它不满足上一条条件吗，所以无法继承y的low值。
计算割点
Tarjan算法告诉我们，如果 \(y\) 是 \(x\) 的子节点且 \(low_y > dfn_x\)。那么 \(x\) 就是割点。
为什么呢？因为根据树的定义，\(y\) 有且仅有一条边连向它的祖先(包括他父节点\(x\))。那如果 \(y\) 除了这条连向祖先的边，只能访问到比\(x\)后遍历到的结点（也就是 \(dfn\) 比 \(dfn_x\) 还大 的结点）。也就意味着如果把 \((x,y)\) 这条边给断掉了，\(y\)无法访问到比\(x\)的dfn小的结点。那么就不连通了，所以此时 \(x\) 就是割点。
但是：这个对于根节点肯定是行不通的！！
就像上面的那个图，
如果根节点用以上方法判定，那就会判定成割点，但是显然不是。所以引出了新的判断根节点的方式：如果搜索树的根节点有两棵即以上的子树，那么根节点为割点。显然，如果把根节点割去，那么两个子树不互相连通，即为割点。
OI-wiki P3388 代码
/*
洛谷 P3388 【模板】割点（割顶）
*/
#include <bits/stdc++.h>
using namespace std;
int n, m; // n：点数 m：边数
int dfn[100001], low[100001], inde, res;
// dfn：记录每个点的时间戳
// low：能不经过父亲到达最小的编号，inde：时间戳，res：答案数量
bool vis[100001], flag[100001]; // flag: 答案 vis：标记是否重复
vector<int> edge[100001]; // 存图用的
void Tarjan(int u, int father) { // u 当前点的编号，father 自己爸爸的编号
vis[u] = true; // 标记
low[u] = dfn[u] = ++inde; // 打上时间戳
int child = 0; // 每一个点儿子数量
for (auto v : edge[u]) { // 访问这个点的所有邻居 （C++11）
if (!vis[v]) {
child++; // 多了一个儿子
Tarjan(v, u); // 继续
low[u] = min(low[u], low[v]); // 更新能到的最小节点编号
if (father != u && low[v] >= dfn[u] &&
!flag
[u]) // 主要代码
// 如果不是自己，且不通过父亲返回的最小点符合割点的要求，并且没有被标记过
// 要求即为：删了父亲连不上去了，即为最多连到父亲
{
flag[u] = true;
res++; // 记录答案
}
} else if (v != father)
low[u] =
min(low[u], dfn[v]); // 如果这个点不是自己，更新能到的最小节点编号
}
if (father == u && child >= 2 &&
!flag[u]) { // 主要代码，自己的话需要 2 个儿子才可以
flag[u] = true;
res++; // 记录答案
}
}
int main() {
cin >> n >> m; // 读入数据
for (int i = 1; i <= m; i++) { // 注意点是从 1 开始的
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
} // 使用 vector 存图
for (int i = 1; i <= n; i++) // 因为 Tarjan 图不一定连通
if (!vis[i]) {
inde = 0; // 时间戳初始为 0
Tarjan(i, i); // 从第 i 个点开始，父亲为自己
}
cout << res << endl;
for (int i = 1; i <= n; i++)
if (flag[i]) cout << i << " "; // 输出结果
return 0;
}