『笔记』tarjan 双连通分量，强连通分量

然后就是庞大的主函数了（提醒一下，在我的理解中root应该只出现在求割点的时候，其他时候基本木有）

• 首先，初始值设为1，编号从\(2\)开始建立双边（如果是单向的你也要建立，因为割点只存在于无向图中）
• 然后进行\(Tarjan\)处理
• 当我们找完的时候，所有的点双和割点都已经被我们求出来啦
• 然后我们就可以愉快的找出每一个点双里的元素
• 此时，我们的所有点双已经被标完编号了，然后就开始给所有的割点建立新编号\(new-id\)
• 建立完以后还是编号从\(2\)开始分别找每个点双里面的割点，然后向他连双向边，然后把其他不是割点的点统计一下所在的点双编号
• 最后输出就好了！完美结束

强连通分量

• 对于一个有向图，若关于任意的两节点\(x,y\)，既存在从\(x\)到\(y\)的路径，同时也存在\(y\)到\(x\)的路径,则称该有向图是强连通图。

• 对于有向图的极大强连通子图称为强连通分量，记为\(SCC\)

• \(Tarjan\)算法能够在线性时间内求解有向图所有的强连通分量

特殊定义

• 给定一个有向图\(G=(V,E)\),存在\(r\in V\)，\(r\)能到达\(V\)中的任何点，则称\(G\)是一个流图，记为\((G,r)\),\(r\)称作\(G\)的源点

• 与无向图类似，在流图上从\(r\)出发开始DFS，每个节点只访问一次

• 所有发生递归的边构成一棵以\(r\)为根的树，称之为流图\(（G,r）\)的搜索树

• 按照每个节点第一次访问的时间顺序依次标号，该整数标号称为时间戳，记为\(dfs_x\)

流图中的边

• 流图中的有向边\((x,y)\)一定是一下四种之一：
  1、树枝边，搜索树上的
  2、前向边，不存在于搜索树上，且在搜索树中\(x\)是\(y\)的祖先
  3、后向边，不存在与搜索树上，且在搜索树中\(y\)是\(x\)的祖先
  4、横叉边，不是上述三种情况的边，那么一定有\(dfn_y<=\)dfn_x,否则会在DFS的时候经过\(y\)从而构成树枝边

• 看图理解一下
  

SCC的求法

定义梳理

• 根据定义，这一定是一个环，那么所有的环一定是强连通图

• \(Tarjan\)算法的基本思路就是对于每一个点，都尽量找到与它一起能构成环的所有节点

不同的边的贡献

• 对于一条边\((x,y)\)我们讨论一下他的类型
  1、前向边，对找环没有用，因为在搜索树中本来就存在\(x->y\)的路径
  2、后向边，对找环很有用，因为在搜索树中可以和\(x->y\)的路径构成一个环
  3、横叉边，对找环可能有用，如果从\(y\)出发能找到一条路径回到\(x\)的祖先节点，则可以构成一个环，它就是有用的

遍历

• 为了找到通过后向边和横叉边构成的环，\(Tarjan\)算法在DFS是维护一个栈

• 当第一次访问到这个点时，入栈

• 访问到\(x\)时，栈中保存了一下的两类点：
  1、搜索树上\(x\)的祖先节点
  2、已经访问过，存在一条路径能够到达\(x\)的祖先的点

• 这些节点都存在一条到达\(x\)的路径，如果\(x\)也能到达他们，那么就构成了一个环

追溯值

• 可以理解为\(x\)的搜索子树上\(x\)能到达的时间戳最小的能到达\(x\)的点

构建方法

• 当第一次访问到\(x\)是，首先令\(low_x=dfn_x\)

-在考虑与\(x\)相连的每一条边，DFS回溯的时候更新\(low_x\)

• 如果\(y\)没有被访问，那么就递归的访问，则\(low_x=min(low_x,low_y)\)

• 但如果\(y\)在栈中，那么\(low_x=min(low_x,dfn_y)\)

• (重点)当\(x\)回溯以前，首先先判断是否有\(low_x=dfn_x\)

• 如果有，那么久不断弹栈直到\(x\)出栈

• 弹栈的所有节点构成了一个SCC

构建理解

• 当我们回溯完毕时，已经考虑了\(x\)能到达的所有节点

• \(y\)被访问过并且不再栈中:\(x\)能达到\(y\),但\(y\)无法到达\(x\)

• 由回溯完毕可知已经考虑了所有\(y\)能到达的节点，所以如果\(y\)能到达\(x\)，那么\((x,y)\)不会是横叉边，所以\(y\)对\(low_x\)没有贡献

缩点法

• 将所有的强连通分量看做一个节点

• 将每个\(SCC\)的编号看做节点的编号，如果两个强连通分量之间有有向边，那么在新图中这两个点之间连上同一个方向的边即可

• 缩掉所有的环之后，就会得到一张DAG，我们就可以在上面做处理

代码实现

void tarjan(int x)
{
	low[x]=dfn[x]=++poi;
	suk[++top]=x;
	ins[x]=1;
	for(int i=head[x];i;i=e[i].last)
	{
		int y=e[i].to;
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		} 
		else if(ins[y])
		low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		sum++;
		int y;
		do{
			y=suk[top--];
			ins[y]=0;
			c[y]=sum;
			scc[sum].push_back(y);
		}while(x!=y);
	}
}

首先进行\(Tarjan\)求出所有的量，然后在回溯之前判断一下即可

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
			tarjan(i); 
	}
	for(int x=1;x<=n;x++)
	{
		for(int i=head[x];i;i=e[i].last)
		{
			int y=e[i].to;
			if(c[x]==c[y]) continue;
			c_add(c[x],c[y]); 
		}
	}
}

在主函数中，遍历完一遍以后，开始枚举每个点的所有编号，根据有向图的变得方向进行建边

例题

P3387 P3388 P2341 P3469 P2194 P1262
P1262 P2002 P2746 P5058