test/library_checker/graph/two_edge_connected_components.test.cpp

• View this file on GitHub
• Last update: 2022-07-20 01:24:27+09:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• 二重辺連結成分分解 (graph/two_edge_connected_components.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#include <bits/stdc++.h>
using namespace std;
#include "../../../graph/two_edge_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);
    E[b].push_back(a);
  }
  two_edge_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/two_edge_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"
#include <bits/stdc++.h>
using namespace std;
#line 2 "graph/two_edge_connected_components.hpp"
/**
 * @brief 二重辺連結成分分解
*/
struct two_edge_connected_components{
  vector<int> tcc;
  int cnt = 0;
  two_edge_connected_components(vector<vector<int>> &E){
    int N = E.size();
    vector<int> p(N, -1);
    vector<int> d(N, -1);
    vector<int> imos(N, 0);
    for (int i = 0; i < N; i++){
      if (p[i] == -1){
        d[i] = 0;
        dfs1(E, p, d, imos, i);
      }
    }
    tcc = vector<int>(N, -1);
    for (int i = 0; i < N; i++){
      if (tcc[i] == -1){
        tcc[i] = cnt;
        cnt++;
        dfs2(E, p, imos, i);
      }
    }
  }
  void dfs1(vector<vector<int>> &E, vector<int> &p, vector<int> &d, vector<int> &imos, int v = 0){
    bool pe = false;
    for (int w : E[v]){
      if (w != p[v] || pe){
        if (d[w] == -1){
          p[w] = v;
          d[w] = d[v] + 1;
          dfs1(E, p, d, imos, w);
          imos[v] += imos[w];
        } else if (d[w] < d[v]){
          imos[v]++;
          imos[w]--;
        }
      } else {
        pe = true;
      }
    }
  }
  void dfs2(vector<vector<int>> &E, vector<int> &p, vector<int> &imos, int v = 0){
    for (int w : E[v]){
      if (tcc[w] == -1){
        if (imos[w] > 0){
          tcc[w] = tcc[v];
        } else {
          tcc[w] = cnt;
          cnt++;
        }
        dfs2(E, p, imos, w);
      }
    }
  }
  int operator [](int v){
    return tcc[v];
  }
};
#line 5 "test/library_checker/graph/two_edge_connected_components.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);
    E[b].push_back(a);
  }
  two_edge_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