关于点双和边双的求法

点双

一个点为割点当且仅当:

  • 非根节点无返祖边,即 \(dfn_x \leq low_v\)
  • 根节点有两个儿子以上

所以不用开栈

void Tarjan(int x){
    dfn[x] = low[x] = ++ tim; int sz = 0;
    for(int i = head[x]; i; i = e[i].then){
        int v = e[i].to;
        if(!dfn[v]){
            Tarjan(v); sz ++;
            low[x] = min(low[x], low[v]);
            if(low[v] >= dfn[x] && x != root) orz[x] = 1;
        }
        else low[x] = min(low[x], dfn[v]);
    }
    if(x == root && sz >= 2) orz[x] = 1;
}

摘自本人在模板题中的代码

边双

在\(Tarjan\)时判断一下不能走回父亲,其他与强连通分量一样

void Tarjan(int x, int fa){
    dfn[x] = low[x] = ++ tim;
    sta[++top] = x; vis[x] = 1;
    for(int i = head[x]; i; i = e[i].then){
        int v = e[i].to;
        if(!dfn[v] && v != fa){
            Tarjan(v, x);
            low[x] = min(low[x], low[v]); 
        }
        else if(vis[v] && v != fa) low[x] = min(low[x], dfn[v]);
    }

    if(low[x] == dfn[x]){
        cnt ++; int yy;
        while(yy = sta[top--]){
            vis[yy] = 0;
            ans[cnt] ^= val[yy];
            if(yy == x) break;
        }
    }
}

摘自本人在模板题中的代码

注意

本文仅提供做法,无严谨证明,仅供参考
可能以后会补吧

上一篇:LOJ10015扩散


下一篇:蓝桥杯-【剪邮票】【2016年省赛B组题解】--bfs+全排列