test/yosupo/scc.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 18:08:33+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• graph/stronglyconnectedcomponent.cpp

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../graph/stronglyconnectedcomponent.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  SCC G(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    G.add_edge(a,b);
  }
  int k=G.build();
  cout<<k<<endl;
  for(int i=0;i<k;i++){
    cout<<G.C[i].size();
    for(int v:G.C[i]) cout<<" "<<v;
    cout<<"\n";
  }
  cout<<flush;
  return 0;
}

#line 1 "test/yosupo/scc.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "graph/stronglyconnectedcomponent.cpp"

#line 3 "graph/stronglyconnectedcomponent.cpp"
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 8 "test/yosupo/scc.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  SCC G(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    G.add_edge(a,b);
  }
  int k=G.build();
  cout<<k<<endl;
  for(int i=0;i<k;i++){
    cout<<G.C[i].size();
    for(int v:G.C[i]) cout<<" "<<v;
    cout<<"\n";
  }
  cout<<flush;
  return 0;
}

Back to top page