[学习笔记]tarjan([study notes] tarjan)

强连通分量

时间复杂度:\(O(n+m)\)
用途:有向图缩环

int f[N],dfn[N],low[N],sta[N],top;
/*dfn[u]:遍历到u点的时间; low[u]:u点可到达的各点中最小的dfn[v],即最高层的点*/
bool ins[N];
inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    sta[++top]=u;ins[u]=true;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]);
        }
        else if(ins[e[i].to])
            low[u]=min(low[u],low[e[i].to]);
    if(dfn[u]==low[u]){
        while(sta[top+1]!=u){
            f[sta[top]]=u;
            ins[sta[top--]]=false;
        }
    }
}
inline void solve(){
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
}

割边

割边,又称桥.

\(dfn[\;],low[\;]\)的定义同\(tarjan\)求有向图强连通分量.

枚举当前点\(u\)的所有邻接点\(v\):

1.如果某个邻接点\(v\)未被访问过,则访问\(v\),并在回溯后更新\(low[u]=min(low[u],low[v])\);

2.如果某个邻接点\(v\)已被访问过,则更新\(low[u]=min(low[u],dfn[v])\).

对于当前节点\(u\),如果邻接点中存在一点\(v\)满足\(low[v]>dfn[u]\)(\(v\)向上无法到达\(u\)及\(u\)祖先)说明\((u,v)\)为一条割边.

inline void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to,u);
            low[u]=min(low[u],low[e[i].to]);
            if(low[e[i].to]>dfn[u]) cut[e[i].n]=true; 
        }
        else if(e[i].to!=fa)
            low[u]=min(low[u],dfn[e[i].to]);
}

割点

\(dfn[\;],low[\;]\)的定义同\(tarjan\)求有向图强连通分量.

枚举当前点\(u\)的所有邻接点\(v\):

1.如果某个邻接点\(v\)未被访问过,则访问\(v\),并在回溯后更新\(low[u]=min(low[u],low[v])\);

2.如果某个邻接点\(v\)已被访问过,则更新\(low[u]=min(low[u],dfn[v])\).

对于当前节点\(u\),

如果\(u\)为搜索树中的根节点,若它的子节点数\(\geq2\)(根是多棵子树上节点的唯一连通方式),则\(u\)为割点;

如果\(u\)为搜索树上的非根节点,若存在子节点\(v\)满足\(low[v]\;\geq\;dfn[u]\)(\(v\)向上无法到达\(u\)的祖先),则\(u\)为割点.

inline void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=g[u];i;i=e[i].nxt){
        ++t[u];
        if(!dfn[e[i].to]){
            tarjan(e[i].to,u);
            low[u]=min(low[u],low[e[i].to]);
            if(u==rt){
                if(t[u]>=2) cut[u]=true;
            }
            else if(low[e[i].to]>=dfn[u]) cut[u]=true;
        }
        else if(e[i].to!=fa)
            low[u]=min(low[u],dfn[e[i].to]);
    }
}

2017-01-26 19:18:26

2017-01-26 19:18:26

————————

Strongly connected component

Time complexity: \ (O (n + m) \)
Purpose: digraph ring

int f[N],dfn[N],low[N],sta[N],top;
/*dfn[u]:遍历到u点的时间; low[u]:u点可到达的各点中最小的dfn[v],即最高层的点*/
bool ins[N];
inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    sta[++top]=u;ins[u]=true;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]);
        }
        else if(ins[e[i].to])
            low[u]=min(low[u],low[e[i].to]);
    if(dfn[u]==low[u]){
        while(sta[top+1]!=u){
            f[sta[top]]=u;
            ins[sta[top--]]=false;
        }
    }
}
inline void solve(){
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
}

Edge cutting

Cutting edge, also known as bridge

\The definition of (DFN [\;], low [\;] \) is the same as that of \ (tarjan \) to find the strongly connected component of a directed graph

Enumerate all adjacency points \ (V \) of the current point \ (U \):

1. If an adjacent contact \ (V \) has not been accessed, access \ (V \) and update \ (low [u] = min (low [u], low [v]) after backtracking \;

2. If an adjacent contact \ (V \) has been accessed, update \ (low [u] = min (low [u], DFN [v])

For the current node \ (U \), if there is a point \ (V \) in the adjacent point that satisfies \ (low [v] & gt; DFN [u] \) (\ (V \) cannot reach \ (U \) and \ (U \) ancestors upward), it indicates that \ ((U, V) \) is a cutting edge

inline void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=g[u];i;i=e[i].nxt)
        if(!dfn[e[i].to]){
            tarjan(e[i].to,u);
            low[u]=min(low[u],low[e[i].to]);
            if(low[e[i].to]>dfn[u]) cut[e[i].n]=true; 
        }
        else if(e[i].to!=fa)
            low[u]=min(low[u],dfn[e[i].to]);
}

Cut point

\The definition of (DFN [\;], low [\;] \) is the same as that of \ (tarjan \) to find the strongly connected component of a directed graph

Enumerate all adjacency points \ (V \) of the current point \ (U \):

1. If an adjacent contact \ (V \) has not been accessed, access \ (V \) and update \ (low [u] = min (low [u], low [v]) after backtracking \;

2. If an adjacent contact \ (V \) has been accessed, update \ (low [u] = min (low [u], DFN [v])

For the current node \ (U \),

If \ (U \) is the root node in the search tree, if its number of child nodes \ (\ geq2 \) (the root is the only way to connect nodes on multiple sub trees), then \ (U \) is the cut point;

If \ (U \) is a non root node in the search tree, if there are child nodes \ (V \) that meet \ (low [v] \; \ GEQ \; DFN [u] \) (\ (V \) cannot reach the ancestor of \ (U \) upward), then \ (U \) is the cut point

inline void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    for(int i=g[u];i;i=e[i].nxt){
        ++t[u];
        if(!dfn[e[i].to]){
            tarjan(e[i].to,u);
            low[u]=min(low[u],low[e[i].to]);
            if(u==rt){
                if(t[u]>=2) cut[u]=true;
            }
            else if(low[e[i].to]>=dfn[u]) cut[u]=true;
        }
        else if(e[i].to!=fa)
            low[u]=min(low[u],dfn[e[i].to]);
    }
}

2017-01-26 19:18:26

2017-01-26 19:18:26