src/graph/lowlink.hpp

• View this file on GitHub
• Last update: 2026-03-17 19:58:42+09:00
• Include: #include "src/graph/lowlink.hpp"

Depends on

• src/template.hpp

Verified with

• src/test/aoj_GRL_3_A.cpp
• src/test/aoj_GRL_3_B.cpp

Code

#include "../template.hpp"

struct LowLink{
    vector<vector<int>> G;
    vector<int> ord,low,vis,isa;    
    int dfs(int v, int p, int t){
        vis[v]=1;
        ord[v]=t++;
        low[v]=ord[v];
        int cnt=0;
        for(int e: G[v]){
            if(!vis[e]){
                cnt++;
                t=dfs(e,v,t);
                chmin(low[v], low[e]);
                if(~p&&ord[v]<=low[e])isa[v]=1;
                if(p==-1&&cnt==2)isa[v]=1;
            }
            else if(e!=p){
                chmin(low[v],ord[e]);
            }
        }
        return t;
    }
    
    LowLink(vector<vector<int>> G): G(G) {
        int N=si(G);
        ord.assign(N,0);
        low.assign(N,0);
        vis.assign(N,0);
        isa.assign(N,0);
        int t=0;
        rep(i,si(G)){
            if(!vis[i]){
                t=dfs(i,-1,t);
            }
        }
    }
    bool is_bridge(int u, int v){
        if(ord[u]>ord[v])swap(u,v);
        return ord[u]<low[v];
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 2 "src/graph/lowlink.hpp"

struct LowLink{
    vector<vector<int>> G;
    vector<int> ord,low,vis,isa;    
    int dfs(int v, int p, int t){
        vis[v]=1;
        ord[v]=t++;
        low[v]=ord[v];
        int cnt=0;
        for(int e: G[v]){
            if(!vis[e]){
                cnt++;
                t=dfs(e,v,t);
                chmin(low[v], low[e]);
                if(~p&&ord[v]<=low[e])isa[v]=1;
                if(p==-1&&cnt==2)isa[v]=1;
            }
            else if(e!=p){
                chmin(low[v],ord[e]);
            }
        }
        return t;
    }
    
    LowLink(vector<vector<int>> G): G(G) {
        int N=si(G);
        ord.assign(N,0);
        low.assign(N,0);
        vis.assign(N,0);
        isa.assign(N,0);
        int t=0;
        rep(i,si(G)){
            if(!vis[i]){
                t=dfs(i,-1,t);
            }
        }
    }
    bool is_bridge(int u, int v){
        if(ord[u]>ord[v])swap(u,v);
        return ord[u]<low[v];
    }
};

Back to top page