Lowlink
(Graph/lowlink.hpp)

• View this file on GitHub
• Last update: 2024-01-12 04:16:01+09:00
• Include: #include "Graph/lowlink.hpp"

Verified with

• Verify/LC_two_edge_connected_components.test.cpp

Code

#pragma once

struct LowLink{
    const int n; vector<vector<int>> g;
    vector<int> used,ord,low,id,arti;
    LowLink(const int& _n=0):n(_n),g(n),
        used(n,0),ord(n,0),low(n,0),id(n,-1){
    }
    void add_edge(int u,int v){
        g[u].emplace_back(v); g[v].emplace_back(u);
     }
    void dfs(int v,int p,int& k){
        used[v]=1; low[v]=ord[v]=k++;
        bool isarti=0;
        int cnt=0,sub=0;
        for(auto& to:g[v]){
            if(to==p and (++sub)<=1)continue;
            if(!used[to]){
                cnt++; dfs(to,v,k);
                chmin(low[v],low[to]);
                isarti|=(p>=0&&low[to]>=ord[v]);
            }
            else chmin(low[v],ord[to]);
        }
        isarti|=(p==-1&&cnt>1);
        if(isarti)arti.push_back(v);
    }
    void dfs2(int v,int p,int& k){
        if(p!=-1 and ord[p]>=low[v])id[v]=id[p];
        else id[v]=k++;
        for(auto& to:g[v])if(id[to]==-1)dfs2(to,v,k);
    }
    int run(){
        int k=0; rep(i,0,n)if(!used[i])dfs(i,-1,k);
        k=0; rep(i,0,n)if(id[i]==-1)dfs2(i,-1,k);
        return k;
    }
};

/**
 * @brief Lowlink
 */

#line 2 "Graph/lowlink.hpp"

struct LowLink{
    const int n; vector<vector<int>> g;
    vector<int> used,ord,low,id,arti;
    LowLink(const int& _n=0):n(_n),g(n),
        used(n,0),ord(n,0),low(n,0),id(n,-1){
    }
    void add_edge(int u,int v){
        g[u].emplace_back(v); g[v].emplace_back(u);
     }
    void dfs(int v,int p,int& k){
        used[v]=1; low[v]=ord[v]=k++;
        bool isarti=0;
        int cnt=0,sub=0;
        for(auto& to:g[v]){
            if(to==p and (++sub)<=1)continue;
            if(!used[to]){
                cnt++; dfs(to,v,k);
                chmin(low[v],low[to]);
                isarti|=(p>=0&&low[to]>=ord[v]);
            }
            else chmin(low[v],ord[to]);
        }
        isarti|=(p==-1&&cnt>1);
        if(isarti)arti.push_back(v);
    }
    void dfs2(int v,int p,int& k){
        if(p!=-1 and ord[p]>=low[v])id[v]=id[p];
        else id[v]=k++;
        for(auto& to:g[v])if(id[to]==-1)dfs2(to,v,k);
    }
    int run(){
        int k=0; rep(i,0,n)if(!used[i])dfs(i,-1,k);
        k=0; rep(i,0,n)if(id[i]==-1)dfs2(i,-1,k);
        return k;
    }
};

/**
 * @brief Lowlink
 */

Back to top page