graph/stronglyconnectedcomponent.cpp

• View this file on GitHub
• Last update: 2020-10-27 18:08:33+09:00

Required by

• graph/arborescence_edmond.cpp
• graph/twosatisfiability.cpp

Verified with

• test/aoj/2222.test.cpp
• test/aoj/2309.tarjan.test.cpp
• test/aoj/2309.test.cpp
• test/aoj/2647.test.cpp
• test/aoj/3102.test.cpp
• test/aoj/3183.test.cpp
• test/aoj/GRL_2_B.test.cpp
• test/yosupo/scc.test.cpp
• test/yosupo/two_sat.test.cpp
• test/yukicoder/4387.test.cpp

Code

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct SCC{
  vector< vector<int> > G,R,H,C;
  vector<int> vs,used,blg;
  SCC(int n):G(n),R(n),used(n),blg(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    R[v].emplace_back(u);
  }

  void dfs(int v){
    used[v]=1;
    for(int u:G[v])
      if(!used[u]) dfs(u);
    vs.emplace_back(v);
  }

  void rdfs(int v,int k){
    used[v]=1;
    blg[v]=k;
    C[k].emplace_back(v);
    for(int u:R[v])
      if(!used[u]) rdfs(u,k);
  }

  int build(bool uniq=true){
    int n=G.size();
    for(int v=0;v<n;v++)
      if(!used[v]) dfs(v);

    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=n-1;i>=0;i--){
      if(!used[vs[i]]){
        H.emplace_back();
        C.emplace_back();
        rdfs(vs[i],k++);
      }
    }

    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          H[blg[v]].emplace_back(blg[u]);

    if(uniq){
      for(int i=0;i<k;i++){
        sort(H[i].begin(),H[i].end());
        H[i].erase(unique(H[i].begin(),H[i].end()),H[i].end());
      }
    }
    return k;
  }

  int operator[](int k) const{return blg[k];}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#line 1 "graph/stronglyconnectedcomponent.cpp"

#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct SCC{
  vector< vector<int> > G,R,H,C;
  vector<int> vs,used,blg;
  SCC(int n):G(n),R(n),used(n),blg(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    R[v].emplace_back(u);
  }

  void dfs(int v){
    used[v]=1;
    for(int u:G[v])
      if(!used[u]) dfs(u);
    vs.emplace_back(v);
  }

  void rdfs(int v,int k){
    used[v]=1;
    blg[v]=k;
    C[k].emplace_back(v);
    for(int u:R[v])
      if(!used[u]) rdfs(u,k);
  }

  int build(bool uniq=true){
    int n=G.size();
    for(int v=0;v<n;v++)
      if(!used[v]) dfs(v);

    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=n-1;i>=0;i--){
      if(!used[vs[i]]){
        H.emplace_back();
        C.emplace_back();
        rdfs(vs[i],k++);
      }
    }

    for(int v=0;v<n;v++)
      for(int u:G[v])
        if(blg[v]!=blg[u])
          H[blg[v]].emplace_back(blg[u]);

    if(uniq){
      for(int i=0;i<k;i++){
        sort(H[i].begin(),H[i].end());
        H[i].erase(unique(H[i].begin(),H[i].end()),H[i].end());
      }
    }
    return k;
  }

  int operator[](int k) const{return blg[k];}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

Back to top page