cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ttamx/cp-library

:heavy_check_mark: verify/yosupo/graph/scc.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include "template.hpp"
#include "graph/graph-base.hpp"
#include "graph/strongly-connected-component.hpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    Graph g=read_graph<void,true>(n,m,0);
    auto [k,scc]=strongly_connected_component(g);
    vector<vector<int>> ans(k);
    for(int i=0;i<n;i++)ans[scc[i]].emplace_back(i);
    reverse(ans.begin(),ans.end());
    cout << k << "\n";
    for(auto &v:ans){
        cout << v.size();
        for(auto x:v)cout << " " << x;
        cout << "\n";
    }
}
#line 1 "verify/yosupo/graph/scc.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "graph/graph-base.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-15
 * Description: Graph Base
 */

template<class T>
struct Edge{
    int from,to,id;
    T cost;
    Edge(int _from,int _to,T _cost,int _id):from(_from),to(_to),cost(_cost),id(_id){}
    operator int()const{return to;}
};

template<class T=void,bool directed=false>
struct Graph{
    static constexpr bool is_directed=directed;
    static constexpr bool is_weighted=!is_same<T,void>::value;
    using cost_type = std::conditional_t<is_weighted,T,int>;
    using edge_type = Edge<cost_type>;
    int n,m;
    vector<edge_type> edges;
    vector<vector<edge_type>> g;
    vector<int> _deg,_indeg,_outdeg;
    Graph():n(0),m(0){}
    Graph(int _n):n(_n),m(0),g(_n){}
    vector<edge_type> &operator[](int u){return g[u];}
    void add_edge(int from,int to,cost_type cost=1,int id=-1){
        assert(0<=from&&from<n&&0<=to&&to<n);
        if(id==-1)id=m;
        edges.emplace_back(edge_type(from,to,cost,id));
        g[from].emplace_back(edge_type(from,to,cost,id));
        if(!is_directed)g[to].emplace_back(edge_type(to,from,cost,id));
        m++;
    }
    void calc_deg(){
        _deg.assign(n,0);
        for(auto &e:edges)_deg[e.from]++,_deg[e.to]++;
    }
    void calc_inout_deg(){
        _indeg.assign(n,0);
        _outdeg.assign(n,0);
        for(auto &e:edges)_outdeg[e.from]++,_indeg[e.to]++;
    }
    const vector<int> &deg_array(){
        if(_deg.empty())calc_deg();
        return _deg;
    }
    const vector<int> &indeg_array(){
        if(_indeg.empty())calc_inout_deg();
        return _indeg;
    }
    const vector<int> &outdeg_array(){
        if(_outdeg.empty())calc_inout_deg();
        return _outdeg;
    }
    int deg(int u){return deg_array()[u];}
    int indeg(int u){return indeg_array()[u];}
    int outdeg(int u){return outdeg_array()[u];}
    Graph reverse(){
        assert(is_directed);
        Graph res(n);
        for(auto &e:edges)res.add_edge(e.to,e.from,e.cost,e.id);
        return res;
    }
};

template<class T=void,bool directed=false>
Graph<T,directed> read_graph(int n,int m,int offset=1){
    using G = Graph<T,directed>;
    G g(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        u-=offset,v-=offset;
        if(g.is_weighted){
            typename G::cost_type w;
            cin >> w;
            g.add_edge(u,v,w);
        }else{
            g.add_edge(u,v);
        }
    }
    return g;
}
template<class T=void,bool directed=false>
Graph<T,directed> read_tree(int n,int offset=1){
    return read_graph<T,directed>(n,n-1,offset);
}

#line 2 "graph/strongly-connected-component.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-28
 * Description: Strongly Connected Component.
 */

template<class G>
pair<int,vector<int>> strongly_connected_component(G &g){
    static_assert(G::is_directed);
    int n=g.n;
    vector<int> disc(n,-1),low(n),scc(n,-1);
    stack<int> st;
    vector<bool> in_st(n);
    int t=0,scc_cnt=0;
    function<void(int,int)> dfs=[&](int u,int p){
        disc[u]=low[u]=t++;
        st.emplace(u);
        in_st[u]=true;
        for(int v:g[u]){
            if(disc[v]==-1){
                dfs(v,u);
                low[u]=min(low[u],low[v]);
            }else if(in_st[v]){
                low[u]=min(low[u],disc[v]);
            }
        }
        if(disc[u]==low[u]){
            while(true){
                int v=st.top();
                st.pop();
                in_st[v]=false;
                scc[v]=scc_cnt;
                if(v==u)break;
            }
            scc_cnt++;
        }
    };
    for(int i=0;i<n;i++)if(disc[i]==-1)dfs(i,-1);
    return {scc_cnt,scc};
}

#line 5 "verify/yosupo/graph/scc.test.cpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    Graph g=read_graph<void,true>(n,m,0);
    auto [k,scc]=strongly_connected_component(g);
    vector<vector<int>> ans(k);
    for(int i=0;i<n;i++)ans[scc[i]].emplace_back(i);
    reverse(ans.begin(),ans.end());
    cout << k << "\n";
    for(auto &v:ans){
        cout << v.size();
        for(auto x:v)cout << " " << x;
        cout << "\n";
    }
}
Back to top page