Tarjan学习笔记

集训太棒了

首先,强连通分量的定义:

有向图内,一个强连通分量内任一点之间豆村咋至少一条路径。

直观一点?

一个点集,在有向图上它们构成了一个环(个人理解但的确是这样)

Tarjan学习笔记

一些定义:

Dfn(u)是节点u的时间戳,表示点u是第几个被访问的节点。

Low(u)是u或u的子树能够追溯到的最早的栈中节点的时间戳。

当Dfn(u)=Low(u)时,以u为根的搜索子树上所有节点(从栈顶到u的所有节点)是一个强连通分量。

Low数组的计算方法: 如果x→y是正向边(连接到不在栈中节点的边),

y是x的子树,所以y最早能去哪x最早就能去哪

那么 low[x]=min(low[x],low[y])

 

 

如果x→y是反向边(连接到已在栈中节点的边),这时候我们发现构成环了

那么 low[x]=min(low[x],dfn[y])

 

如果x→y是交叉边(连接到已经出栈的节点的边),

什么也不干

不理解?

 

Tarjan学习笔记

 

Tarjan学习笔记

 

Tarjan学习笔记

 

 

 Tarjan学习笔记

 

code:

int n,m;
#define maxn 10009
vector<int> son[maxn]; 
int tim,size[maxn],belong[maxn],scc_cnt,cnt;
bool bein[maxn];
int st[maxn];
int dfn[maxn],low[maxn];
void Tarjan(int rt)
{
    dfn[rt]=low[rt]=++tim;
    st[++cnt]=rt;
    for(int i=0;i<son[rt].size();i++)
    {
        int to=son[rt][i];
        if(!dfn[to])//正向边 
        {
            Tarjan(to);
            low[rt]=min(low[rt],low[to]);
        }else if(!belong[to])//反向边 
        {
            low[rt]=min(low[rt],dfn[to]);//能不能取到一个更早的点 
        }
    }
    if(dfn[rt]==low[rt])
    {
        //关键节点!! 
        scc_cnt++;
        int k;
        do{
            k=st[cnt--];
            belong[k]=scc_cnt;
            size[scc_cnt]++;
        }while(k!=rt);
    }
}

 

上一篇:图的连通性——Tarjan算法&割边&割点


下一篇:RMQ Tarjan的Sparse-Table算法