tarjan 之点双连通分量的查找
1. 点双连通分量的定义
一个
无向图
中去掉任一个
节点
都不会改变此图的
连通性
那么通俗来讲是什么呢，可以认为这个图中任意两个节点要么被囊括
同在一个环
中，要么这个图
有且仅有两个
节点，而且两个节点
可达
。如下图代表了双连通分量的两种情况
2. tarjan的基础—维护low数组和dfn数组
a) 名词解释
在我们没有看到代码的情况下，任何的名词解释都是苍白的，因为我们没有将其带入；同时，任何没有解释定义变量干什么的代码都是
耍流氓
所以在这里仅仅是初步的介绍，如果还是不了解，相信我，很正常，需要做的就是去了解代码实现，分析定义变量的作用。
dfn
dfn是一个数组，每个项存的是啥呢，存的是一个
时间戳
。时间戳这个说法很有灵性，这么说也无异于啥也没说，我们先来粗略的了解一下tarjan这玩意干了啥，tarjan主要的工作是做了一次
dfs
，dfs相信大家都很熟悉，深度优先搜索，那么深度优先搜索会产生一个什么？
答案是，
深度优先搜索树
。来看下深度优先搜索树是个啥玩意。
拿这个图来说，以1为root进行dfs是个什么过程呢，首先访问到1，接着会有分支，可能会到2或者4，我们选择2（可以选择4，以后再可能产生分支的话，都是随意选择，不再做说明），从2就可以选择3，我们一点点的把搜索到的节点加入到一棵
树
中，并确保父子关系，从1节点出发访问到2节点，那么1节点就是2节点的父节点，最后我们会得到树就是所说的
深度优先搜索树
，叫这个名字是因为这是通过深度优先搜索一个图得到的树。来看看树的模样。
那么说的
时间戳
是个什么东西呢，时间戳就是加入深度优先搜索树的顺序。
low
low的话，也是一个数组，它代表的是什么呢，是在深度优先搜索树来看，以这个节点在接下来的深度优先搜索中可以访问到最小的
dfn
值，这句话并不能很好的解释
最小的不一定是自己吗？
我们在深度优先搜索的过程中，什么时候才会返回呢？
要回答这个问题，还是要新想想深度优先搜索在干什么，访问和递归这个节点的所有连通节点，之前访问过的节点不能再访问。那么什么时候会返回呢，就是当这个节点不存在能继续访问的子节点的时候就返回啦，这个
low
呢，其实就是把
除了父节点
的其它节点都看成了这个节点的可以访问的节点（虽然dfs不是啦，dfs在不能访问时要返回，而low却要更新成在这些节点中最小的那个）。
所以其实，我们除了在
接下来深度优先搜索中
真正去访问的节点，还和那些能够
通过一次访问到达
的节点算入了可以访问到的节点！上图！！！
大家如果还是有点疑惑可以自己按照我写的dfn（主要是为了结果能对上）的顺序dfs一次啦。
b) 那么说的很好，那里可以维护呢
直接上伪代码
dfn[]
low[]
nodes[] // 点集合
fathers[] // 父节点集合
map(node, nodesCanReach[]) // 一个map，每个node都对应一个连接的点集合
timeStack // 时间戳
void tarjan() {
for node in nodes:
if (dfn[node] == 0):
// 说明这个node还没有被访问过， 这个时候呢就要以这个节点为根节点进行一次dfs
// 根节点的父节点是啥呢？不如给一个不可能出现的值，-1好了
father[node] = -1
dfs(node);
}
void dfs(int node) {
dfn = low = ++timeStack // 初始化啦
for (sonNode in map.get(node)):
if (sonNode == father[node]) // 不能逆流而上，想访问父节点，答案是不让
continue;
if (dfn[node] == 0) // 说明这个节点没有被访问过，这就是进入下一次dfs的节奏啊
father[sonNode] = node;
dfs(sonId);
low[node] = min(low[node], low[sonNode])
// 父节点的low肯定是所有子节点里最小的，毋庸置疑，从定义就可以看出来
else // 这个节点被访问过
low[node] = min(low[node], dfn[sonNode])
// 定义定义！
}
3. 怎么利用tarjan寻找点连通分量呢
结合伪代码来解释，上面的伪代码中给出的注释将不再解释，上面已给出的数据的定义也将不再给出，也只展示dfs函数，如果还是不能理解，请结合查看
Stack<node>[] // 一个栈，用来存点，也许很多教程都是存的边，我们来看看能不能通过存点解决
List<BCC[]>[]
BCC[] // 代表找到的一个点双连通分量
void dfs(int node) {
dfn = low = ++timeStack
Stack.push(node) // node入栈
for (sonNode in map.get(node)):
if (sonNode == father[node])
continue;
if (dfn[node] == 0)
father[sonNode] = node;
dfs(sonNode);
low[node] = min(low[node], low[sonNode])
if (low[sonNode] >= dfn[node]) // !!!!!!!!!!这就是找到了双连通分量的标志
clear(BCC) // 清空BCC拉，准备存
do {
popedNode = Stack.pop();
BCC.add(popedNode)
} while (father[popedNode] != node)
BCC.add(node)
List.add(BCC) // 从clear到这里都是出栈操作
else
low[node] = min(low[node], dfn[sonNode])
}
4. 算法的原理
为什么我们得到的BCC就是一个点双连通分量呢
low[sonNode] >= dfn[node]这句话的引申义是什么呢，说明啊，这个sonNode之后可达的全部节点没有一个是比Node更向上的，说明什么呢，说明要么这个子节点一路向下，再也不回头，类似于最上面的第一种情况；要么就是成环了，回到了node上，这就是找到了这个点双连通分量的标志。
也许我们还有的疑惑就是为什么可达的点不包括已经被访问节点的子节点，或者说那句low[node] = min(low[node], dfn[sonNode])为什么不是low[node] = min(low[node], low[sonNode])了，想想，如果访问到了已经访问的节点，说明了什么，说明必然成环了。如果再次访问，就会出现什么？会出现割点！！！
以上均为个人观点，如有错误，轻不吝指教！！