tarjan

缩点

有向图缩点（把一个强连通分量看成一个点），用于优化。

• 树枝边：DFS 时经过的边，即 DFS 搜索树上的边
• 反祖边：也叫回边或后向边，与 DFS 方向相反，从某个结点指
  向其某个祖先的边
• 横叉边：从某个结点指向搜索树中另一子树中的某结点的边，它
  主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结
  点并不是当前结点的祖先时形成的
• 前向边：与 DFS 方向一致，从某个结点指向其某个子孙的边，
  它是在搜索的时候遇到子树中的结点的时候形成的

对于每个点维护两个值 \(（dfn，low）\) ，\(dfn\) 是 \(dfs\) 序，\(low\) 表示这条路走到头能回到祖宗的最小值（或叶子），对于一个点 \(u\) ，如果他的 \(low[u]\) 等于 \(dfn[u]\) ,说明 向下 \(dfs\) 时还能回到 \(u\) ，则中间这部分构成一个强连通分量。
如图，先 \(dfs\) 到 \(e\) ，\(dfn[e]==low[e]\)，发现一个强连通分量，\(e\) 出栈，回溯到 \(b\) ,第二个强连通分量，将 \(b,c,d\) 出栈。
缩完点变成有向无环图（DAG），可以跑最短路，可以dp，很方便。

code

void tj(int s)
{
	dfn[s]=low[s]=++num;
	v[s]=1; st.push(s);
	for(int i=head[s];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(!dfn[to])
		{
			tj(to);
			low[s]=min(low[s],low[to]);
		}
		else if(v[to]) low[s]=min(low[s],dfn[to]);
	}
	if(dfn[s]==low[s])
	{
		int now;
		t++;
		do
		{
			now=st.top(); st.pop();
			v[now]=0; bl[now]=t;
			sz[t]++;
		} while(s!=now);
	}
}
int main()
{
	………… 
	memset(head,0,sizeof(head)); tot=0;
	for(int i=1;i<=m;i++)
		if(bl[x[i]]!=bl[y[i]])
		add(bl[x[i]],bl[y[i]]);
	………… 
}

割点

无向图求割点，就是删掉后能把图隔成几个部分的点，思路和缩点类似，如果 \(dfn[u]<=low[v]\) ,说明 \(u\) 以下有一个连通块，且 \(u\) 下面的连通块和 \(u\) 上面的没有联系，所以此时 \(u\) 为割点。
如图 \(B,E,K\) 为割点。
（注意，根节点如果只有一个儿子，他不是割点。）

code

void tj(int s)
{
	dfn[s]=low[s]=++num;
	int son=0;
	for(int i=head[s];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(!dfn[to])
		{
			tj(to);
			low[s]=min(low[s],low[to]);
			if(dfn[s]<=low[to])
			{
				son++;
				if(s!=root || son>1)
				{
					if(!ans[s]) cnt++;
					ans[s]=1;
				}
			}
		}
		else	
			low[s]=min(low[s],dfn[to]);
	}
}

割边

无向图求割边，定义和割点差不多了，如 \(dfn[u]<low[v]\) 则 \((u,v)\) 为割边（注意不能 \(=\) ），上图割边有 \(A-B\)以及 \(E-K\) 和 \(K-L\) ,因为是无向图，建边时都建成了正向反向两条边，所以要判一下正向反向的两条边，避免原路走回去。

code

void tj(int s,int fa)
{
	dfn[s]=low[s]=++num;
	for(int i=head[s];i;i=e[i].nxt)
	{
		int to=e[i].to;
		if(to==fa) continue;
		if(!dfn[to])
		{
			tj(to,s);
			low[s]=min(low[s],low[to]);
			if(dfn[s]<low[to]) ans++;
		}
		else low[s]=min(low[s],dfn[to]);
	}
}