src/graph/scc.hpp

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

Depends on

src/template.hpp

Code

#include"../template.hpp"

struct scc_graph{
    vector<vector<int>> G,H;
    vector<int> vis;
    stack<int> st;
    int N;
    scc_graph(int n): N(n), G(N),H(N),vis(N,0) {}
    void add_edge(int u, int v){
        G[u].push_back(v);
        H[v].push_back(u);
    }
    void dfs(int v){
        if(vis[v]) return ;
        vis[v]=1;
        for(int e: G[v])dfs(e);
        st.push(v);
    }
    void dfss(int v, vector<int> &V){
        if(vis[v]) return ;
        V.push_back(v);
        for(int e: H[v]){
            dfss(e, V);
        }
    }
    vector<vector<int>> scc(){
        rep(i,N)if(!vis[i])dfs(i);
        fill(all(vis),0);
        vector<vector<int>> gr;
        while(si(st)){
            int v=st.top();
            st.pop();
            if(vis[v]) continue;
            gr.push_back({});
            dfss(v, gr.back());
        }
        return gr;
    }
};

#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/scc.hpp"

struct scc_graph{
    vector<vector<int>> G,H;
    vector<int> vis;
    stack<int> st;
    int N;
    scc_graph(int n): N(n), G(N),H(N),vis(N,0) {}
    void add_edge(int u, int v){
        G[u].push_back(v);
        H[v].push_back(u);
    }
    void dfs(int v){
        if(vis[v]) return ;
        vis[v]=1;
        for(int e: G[v])dfs(e);
        st.push(v);
    }
    void dfss(int v, vector<int> &V){
        if(vis[v]) return ;
        V.push_back(v);
        for(int e: H[v]){
            dfss(e, V);
        }
    }
    vector<vector<int>> scc(){
        rep(i,N)if(!vis[i])dfs(i);
        fill(all(vis),0);
        vector<vector<int>> gr;
        while(si(st)){
            int v=st.top();
            st.pop();
            if(vis[v]) continue;
            gr.push_back({});
            dfss(v, gr.back());
        }
        return gr;
    }
};