test/library_checker/graph/scc.test.cpp

• View this file on GitHub
• Last update: 2022-08-24 04:05:14+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• 強連結成分分解 (graph/strongly_connected_components.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
using namespace std;
#include "../../../graph/strongly_connected_components.hpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    E[a].push_back(b);
  }
  strongly_connected_components G(E);
  int K = G.cnt;
  vector<vector<int>> v(K);
  for (int i = 0; i < N; i++){
    v[G[i]].push_back(i);
  }
  cout << K << endl;
  for (int i = 0; i < K; i++){
    int l = v[i].size();
    cout << l;
    for (int j = 0; j < l; j++){
      cout << ' ' << v[i][j];
    }
    cout << endl;
  }
}

#line 1 "test/library_checker/graph/scc.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
using namespace std;
#line 2 "graph/strongly_connected_components.hpp"
/**
 * @brief 強連結成分分解
*/
struct strongly_connected_components{
  vector<int> scc;
  int cnt = 0;
  void dfs1(vector<vector<int>> &E, vector<int> &t, vector<bool> &used, int v){
    for (int w : E[v]){
      if (!used[w]){
        used[w] = true;
        dfs1(E, t, used, w);
      }
    }
    t.push_back(v);
  }
  void dfs2(vector<vector<int>> &E2, vector<bool> &used2, int v){
    scc[v] = cnt;
    for (int w : E2[v]){
      if (!used2[w]){
        used2[w] = true;
        dfs2(E2, used2, w);
      }
    }
  }
  strongly_connected_components(vector<vector<int>> &E){
    int N = E.size();
    vector<vector<int>> E2(N);
    for (int i = 0; i < N; i++){
      for (int j : E[i]){
        E2[j].push_back(i);
      }
    }
    vector<int> t;
    vector<bool> used(N, false);
    for (int i = 0; i < N; i++){
      if (!used[i]){
        used[i] = true;
        dfs1(E, t, used, i);
      }
    }
    reverse(t.begin(), t.end());
    vector<bool> used2(N, false);
    scc = vector<int>(N);
    for (int i = 0; i < N; i++){
      if (!used2[t[i]]){
        used2[t[i]] = true;
        dfs2(E2, used2, t[i]);
        cnt++;
      }
    }
  }
  int operator [](int k){
    return scc[k];
  }
};
#line 5 "test/library_checker/graph/scc.test.cpp"
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int a, b;
    cin >> a >> b;
    E[a].push_back(b);
  }
  strongly_connected_components G(E);
  int K = G.cnt;
  vector<vector<int>> v(K);
  for (int i = 0; i < N; i++){
    v[G[i]].push_back(i);
  }
  cout << K << endl;
  for (int i = 0; i < K; i++){
    int l = v[i].size();
    cout << l;
    for (int j = 0; j < l; j++){
      cout << ' ' << v[i][j];
    }
    cout << endl;
  }
}

Back to top page