2017.10.29闵神讲课DAY2（tarjan）

tarjan算法

tarjan可以用来求无向图的割点 割边 或有向图的强连通分量

求割点 割边

那么什么是割点割边呢？
割点：在一个无向连通图中，如果去掉这个点以及连向它的边，那么这个图不再连通，那么这个点就是割点
割边：如果去掉某一条边之后，联通分量的数目变多，那么这个点就是割边

用最暴力的方法当然可以求 即给每个点打上标记去枚举 跑一遍dfs即可 但是时间复杂度很不优秀
用tarjan算法可以在O（n+m）求完所有的割点 割边 时间复杂度十分优秀

首先我们要先建一颗dfs树

举个例子：

割边

用low数组来记录dfs中每个点沿着除了父亲之外的所有点能访问到的最小dfn值

我们设x为y的父亲节点

那么如果low[y]<=dfn[x]就是（x，y）不是割边的必要条件（仔细思考一下）
那么我们只要求出low数组即可

那么怎么求low数组和dfs值呢？？

伪代码：

dfn[],low[]
tot;
void dfs(int x,edge e)
{dfn[x]=low[x]=++tot;for((x,y)∈E&&(y,x)!=e)if(!dfn[y]){ dfs(y,(x,y))if(low[y]<low[x]) low[x]=low[y];}else if(dfn[y]<low[x])low[x]=dfn[y];
}

割点

那么怎么求割点呢？？
思考一下割边连接的两个点一定都是割点吗？？？

并不是 并不是！

叶子节点呢？？不是莫大了

那么割边连接的两个点除了叶子节点都是割点吗？？

好像是的 没错就是这样

如果设割边的集合为A 割点的集合为B
我们不能说A=B 因为还有其他重边的情况
也就是说割点不一定与割边相连
但是我们可以说A⊇B
那么我们来思考一下如何求割点呢？？？

其实差不了太多

就是要判断（x，y）是否存在low[y]>=dfn[x]

即对于任意一个x，如果存在（x，y）∈E y∈x son
low[y]>=dfn[x]
则x是割点

思考一下上面的话有漏洞吗？？
如果x是根节点呢 那不就GG

但是如果根节点的子树个数>=2的话 根节点还是一个割点
因此我们要加一个判断
（son>=2||(son==1&&x!=root)）
其他的代码与割边类似 就不在给出了

强连通分量

这时还要记录dfn 和 low
但此时的low数组就没有限制了（不需要不能经过父节点）

此时我们就可以设计算法了，dfs访问到x时，将x加入栈中，对于x出边指向的点y：1.若y未被访问过，递归访问y之后用low[y]更新low[x],2.若y被访问过且y在栈中，那么用dfn[y]更新low[x]。在递归结束如果dfn[x]==low[x],将x及之后的点弹出栈，标记它们属于同一个强连通分量。

大致代码如下：

int tot,bel[MAXV+D];//tot代表强连通分量总数，bel数组代表点属于第几个连通分量
int dfn[MAX+D],low[MAXV+D],ind=0;
int stack[MAXV+D],top;
bool ins[MAXV+D];
void tarjan(int x)