test/yosupo/two_edge_connected_components.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

• Incremental-Bridge-Connectivity (二辺連結成分) (src/Graph/IncrementalBridgeConnectivity.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Graph/IncrementalBridgeConnectivity.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 IncrementalBridgeConnectivity ibc(N);
 for (int i= 0, a, b; i < M; i++) cin >> a >> b, ibc.add_edge(a, b);
 int n= 0;
 vector<int> ans[N];
 for (int i= 0; i < N; ++i) {
  int j= ibc.leader(i);
  ans[j].push_back(i);
  if (ans[j].size() == 1) ++n;
 }
 cout << n << '\n';
 for (int i= 0; i < N; ++i)
  if (!ans[i].empty()) {
   cout << ans[i].size();
   for (int v: ans[i]) cout << " " << v;
   cout << '\n';
  }
 return 0;
}

#line 1 "test/yosupo/two_edge_connected_components.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/two_edge_connected_components
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 2 "src/Graph/IncrementalBridgeConnectivity.hpp"
#include <utility>
#line 4 "src/Graph/IncrementalBridgeConnectivity.hpp"
class IncrementalBridgeConnectivity {
 std::vector<int> cp, bp, bbf, z;
 int t;
 inline int crt(int v) { return cp[v] < 0 ? v : cp[v]= crt(cp[v]); }
 inline int par(int v) { return bbf[v] < 0 ? -1 : leader(bbf[v]); }
public:
 IncrementalBridgeConnectivity(int n): cp(n, -1), bp(n, -1), bbf(n, -1), z(n), t(0) {}
 inline int leader(int v) { return bp[v] < 0 ? v : bp[v]= leader(bp[v]); }
 int size(int v) { return -bp[leader(v)]; }
 bool two_edge_connected(int u, int v) { return leader(u) == leader(v); }
 bool connected(int u, int v) { return crt(u) == crt(v); }
 void add_edge(int u, int v) {
  int a= crt(u= leader(u)), b= crt(v= leader(v));
  if (a == b)
   for (++t, a= u, b= v;;) {
    if (z[a] == t) {
     for (int w: {u, v})
      for (int p; w= leader(w), w != a; bp[a]+= bp[w], bp[w]= a, w= p)
       if (p= bbf[w], bbf[w]= bbf[a]; bp[a] > bp[w]) std::swap(w, a);
     return;
    }
    if (z[a]= t, a= par(a); b != -1) std::swap(a, b);
   }
  if (cp[a] < cp[b]) std::swap(u, v), cp[a]+= cp[b], cp[b]= a;
  else cp[b]+= cp[a], cp[a]= b;
  for (int p; u != -1; u= p) p= par(u), bbf[u]= v, v= u;
 }
};
#line 7 "test/yosupo/two_edge_connected_components.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 IncrementalBridgeConnectivity ibc(N);
 for (int i= 0, a, b; i < M; i++) cin >> a >> b, ibc.add_edge(a, b);
 int n= 0;
 vector<int> ans[N];
 for (int i= 0; i < N; ++i) {
  int j= ibc.leader(i);
  ans[j].push_back(i);
  if (ans[j].size() == 1) ++n;
 }
 cout << n << '\n';
 for (int i= 0; i < N; ++i)
  if (!ans[i].empty()) {
   cout << ans[i].size();
   for (int v: ans[i]) cout << " " << v;
   cout << '\n';
  }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	example_01	AC	5 ms	4 MB
g++-13	example_02	AC	5 ms	4 MB
g++-13	large_cycle_00	AC	32 ms	9 MB
g++-13	max_random_00	AC	72 ms	15 MB
g++-13	max_random_01	AC	69 ms	15 MB
g++-13	max_random_02	AC	68 ms	15 MB
g++-13	random_1_00	AC	47 ms	10 MB
g++-13	random_1_01	AC	53 ms	12 MB
g++-13	random_1_02	AC	27 ms	6 MB
g++-13	random_2_00	AC	17 ms	4 MB
g++-13	random_2_01	AC	8 ms	4 MB
g++-13	random_2_02	AC	22 ms	5 MB
g++-13	random_2_03	AC	29 ms	5 MB
g++-13	random_2_04	AC	14 ms	4 MB
g++-13	small_random_1_00	AC	5 ms	4 MB
g++-13	small_random_1_01	AC	5 ms	4 MB
g++-13	small_random_1_02	AC	5 ms	4 MB
g++-13	small_random_2_00	AC	5 ms	4 MB
g++-13	small_random_2_01	AC	5 ms	4 MB
g++-13	small_random_2_02	AC	5 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	example_01	AC	4 ms	4 MB
clang++-18	example_02	AC	4 ms	4 MB
clang++-18	large_cycle_00	AC	33 ms	9 MB
clang++-18	max_random_00	AC	67 ms	15 MB
clang++-18	max_random_01	AC	68 ms	15 MB
clang++-18	max_random_02	AC	69 ms	15 MB
clang++-18	random_1_00	AC	47 ms	10 MB
clang++-18	random_1_01	AC	51 ms	12 MB
clang++-18	random_1_02	AC	28 ms	6 MB
clang++-18	random_2_00	AC	17 ms	4 MB
clang++-18	random_2_01	AC	8 ms	4 MB
clang++-18	random_2_02	AC	23 ms	5 MB
clang++-18	random_2_03	AC	30 ms	5 MB
clang++-18	random_2_04	AC	14 ms	4 MB
clang++-18	small_random_1_00	AC	5 ms	4 MB
clang++-18	small_random_1_01	AC	5 ms	4 MB
clang++-18	small_random_1_02	AC	5 ms	4 MB
clang++-18	small_random_2_00	AC	5 ms	4 MB
clang++-18	small_random_2_01	AC	5 ms	4 MB
clang++-18	small_random_2_02	AC	5 ms	4 MB

Back to top page