一、基本概念：
流图：
给定一个有向图G= （V，E），若存在r∈V满足，满足从r出发能够到达V中所有的点，则称G是一个流图，记为（G，r），其中r是流图的源点。
流图的搜索树：
在一个流图（G,r）上从r出发，进行深度优先遍历（DFS），每个点只访问一次。所有发生递归的变（x,y）（换言之，从x到y是对y的第一次访问）构成的一棵以r为根的树我们把它称为流图（G,r）的搜索树。
时间戳：
同时，我们在深度优先遍历的过程中按照每个节点第一次被访问的时间顺序，依次给予流图中每个点1~n的标记，该点的标记被称作时间戳，用dfn[x]表示。
边的分类：
对于流图中的有向边（x，y），必是以下四种边之一：
树枝边，指的是搜索树中的边，即x是y的父亲节点。
前向边，指的是搜索树中x是y的祖先节点。
后向边，指的是搜索树中y是x的祖先节点。
横叉边，指的是除了以上三种边之外的边，它一定满足dfn[y] <dfn[x]。
二、有向图的强连通分量：
给定一张有向图。若对于图中的任意两个节点x，y，既存在从x到y的路径，也存在从y到x的路径，则称该有向图为强连通图。
有向图的极大强连通子图被称为强连通分量，简记为SCC。此处极大的含义与双连通分量极大的含义类似。
tarjan算法基于有向图的深度优先遍历，能够在线性时间内求出一张有向图的各个强连通分量。
一个环，一定是强连通图。如果既存在从x到y的路径，也存在从y到x的路径，那么x，y显然在一个环中。因此，tarjan算法的基本思路就是对于每个点，尽量找到与它一起能构成环的所有节点。
容易发现前向边（x，y）没有什么用处，因为搜索树上本来就存在从x到y的路径。后向边（x，y）非常有用，因为它可以和搜索树上从y到x的路径一起构成环。横叉边（x，y）视情况而定，如果从y出发能找到一条路径回到x的最先节点，那么（x，y）就是有用的。
为了找到通过后向边和横叉边构成的环，tarjan算法在深度优先遍历的同时维护了一个栈。当访问到节点x时，栈中需要保存以下两类节点：
搜索树上x的祖先节点，即为集合anc（x）。
设y∈anc（x）。若存在后向边（x，y），则（x，y）与y到x的路径一起形成环。
已经访问过，并且存在一条路径到达anc（x）的节点。
设z是一个这样的点，从z出发存在一条路径到达y∈anc（x）。若存在横叉边（x，z），则（x，z）、z到y的路径、y到x的路径形成一个环。
综上所述，栈中的节点就是能与从x出发的后向边和横叉边形成环的节点。进而可以引入追溯值的概念。
追溯值：
设subtree（x）表示流图的搜索树中以x为根的子树。x的追溯值low（x）定义为满足以下条件的节点的最小时间戳：
该点在栈中。
存在一条从subtree（x）出发的有向边，以该点为终点。
根据定义，Tarjan算法按照以下步骤计算追溯值：
当节点x第一次被访问时，把x入栈，初始化low（x）=dfn（x）。
扫描从x出发的每一条边（x，y）：
若y没被访问过，说明（x，y）是树枝边，递归访问y，从y回溯后，令low（x）=min（low（x），low（y））。
若y被访问过并且y在栈中，则令low（x）=min（low（x），dfn（y））。
从x回溯之前，判断是否有low（x）=dfn（x）。若成立，则不断从栈中弹出节点直到x出栈。
三、强连通分量判定法则：
在追溯值的计算过程中，若从x回溯前，有low（x）=dfn（x）成立，则栈中从x到栈顶的所有节点构成一个强连通分量。
我们不再详细证明。大致来说，在计算追溯值的第三步，如果low（x）=dfn（x）那么说明subtree（x）中的节点不能与栈中其他节点一起构成环。另外，因为横叉边的终点时间戳必定小于起点时间戳，所以subtree（x）中的节点也不可能直接到达尚未访问的节点（时间戳更大）。综上所述，栈中从x到栈顶的所有节点不能与其他节点一起构成环。
又因为我们及时进行了判定和出栈操作，所以从x到栈顶的所有节点独立构成一个强连通分量。
下面的程序实现了Tarjan算法，求出数组c，其中c（x）表示x所在的强连通分量的编号。另外，它还求出了vector数组scc，scc（i）记录了编号为i的强连通分量中所有的节点。整张图共有cnt个强连通分量。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#define ll long long
using namespace std;
const int maxn1=100010;
const int maxn2=1000010;
int ver[maxn2],nt[maxn2],head[maxn1];
int dfn[maxn1],low[maxn1];
int st[maxn1],ins[maxn1],c[maxn1];
vector<int>scc[maxn1];
int n,m,tot,num,top,cnt;
void add(int x,int y)
{
ver[++tot]=y;nt[tot]=head[x];
head[x]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
st[++top]=x;
ins[x]=1;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cnt++;
int z;
do
{
z=st[top--];
ins[z]=0;
c[z]=cnt;
scc[cnt].push_back(z);
}while(x!=z);
}
}
int main(void)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=cnt;i++)
{
for(int j=0;j<scc[i].size();j++)
{
printf("%d ",scc[i][j]);
}
putchar('\n');
}
return 0;
}
与无向图e-DCC的缩点类似，我们也可以把每个SCC缩成一个点。对原图中的每个有向边（x，y），若c（x）！=c（y），则在编号为c（x）与编号为c（y）的SCC之间连边。最后，我们会得到一张有向无环图。下面的程序对SCC执行缩点过程，并把新的到的有向无环图保存在另一个邻接表中。
void add_c(int x,int y)
{
vc[++tc]=y;
nc[tc]=hc[x];
hc[x]=tc;
}
for(int x=1;x<=n;x++)
{
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(c[x]==c[y]) continue;
add_c(c[x],c[y]);
}
}
若问最少添加几条有向边，可以把一张任意有向图变成强连通图。设缩点后的有向无环图中有p个零入度点，q个零出度点，那么答案就是max（p，q）。
特别的，如果整张图本身就是一个强连通图（缩点后仅剩一个点），那么答案就为0。
四、有向图的必经点与必经边：
给定一张有向图起点为S，终点为T。若从S到T的每条路径都经过一个点x，则称点x是有向图中从S到T的必经点。
若从S到T的每条路径都经过一条边（x，y），则称这条边是有向图中从S到T的必经边或桥。
有向图的必经点与必经边是一个较难的问题。因为环上的点也可能是必经点，所以不能简单的把强连通分量所点后按照有向无环图来处理。Lenguar----Tarian算法通过计算支配树（Dominator-Tree），能够在O（nlogn）的时间内求出从有向图的指定起点出发，走到每个点的必经点集。（以后的文章会介绍）。
不过值得一提的是，我们有很简单的方法计算有向无环图的必经点与必经边：
（1）在原图中按照拓扑序进行动态规划，求出起点S到图中每个点x的路径条数fs（x）。
（2）在反图上在此按照拓扑序进行动态规划，求出每个点x到终点T的路径条数ft（x）。
显然fs（T）表示从S到T的路径条数。根据乘法原理：
（1）对于一条有向边（x，y），若fs（x） * ft（y）=fs（T），则（x，y）是有向无环图从S到T的必经边。
（2）对于一个点x，若fs（x） * ft（x）=fs（T），则x是有向无环图从S到T的必经点。
但是，路径条数是一个指数级别的整数，通常超过了32位或64位整数的表示范围。受Hash思想的启发，我们可以把路径条数对一个大质数取模后再保存到fs，ft数组中。这样带来的后果是有较小的概率会产生误判。保险起见，若题目时限宽松，我们可以多选取几个质数，分别作为模数计算。
京公网安备 11010502036488号