verify/yosupo/yosupo-two_edge_connected_components.test.cpp

View this file on GitHub
Last update: 2022-07-23 17:38:00-04:00
Problem: https://judge.yosupo.jp/problem/two_edge_connected_components

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/two-edge-connected-components.hpp"

int main() {
	using namespace std;
	ios_base::sync_with_stdio(0);
	int n, m; 
	cin >> n >> m;
	TwoEdgeCC B; B.init(n);
	for (int i = 0; i < m ;i++) {
		int u, v; cin >> u >> v;
		B.ae(u, v);
	}
	B.build();
	cout << B.num_comps << '\n';
	for (int i = 0; i < B.num_comps; i++) {
		cout << (int)B.comps[i].size() << " ";
		for (int v : B.comps[i]) 
			cout << v << " ";
		cout << '\n';
	}
}

#define PROBLEM "https://judge.yosupo.jp/problem/two_edge_connected_components"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct TwoEdgeCC {
	int n, time, num_comps; 
	std::vector<int> ord, low, id; 
	// order encountered, earliest time in subtree, component id

	std::vector<std::vector<int>> adj, comps, tree;
	// adj, comps storage, bridge block tree

	std::vector<std::pair<int, int>> bridge;
	// bridges

	
	void init(int n_) {
		num_comps = time = 0;
		n = n_;
		ord.assign(n, -1);
		low.assign(n, 0);
		id.assign(n, -1);
		adj.assign(n, std::vector<int>());
		comps.clear();
		tree.clear();
	}

	void ae(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	bool is_bridge(int u, int v) {
		if (ord[u] > ord[v])
			std::swap(u, v);
		return ord[u] < low[v];
	}

	void dfs(int src, int par) {
		ord[src] = low[src] = time++;
		bool bic = false; // accounts for double edges

		for (int nxt : adj[src]) { 
			if (nxt == par && !bic) {
				bic = true;
				continue;
			}
			if (ord[nxt] != -1) {
				low[src] = std::min(low[src], ord[nxt]);
				continue;
			}
			dfs(nxt, src);
			low[src] = std::min(low[src], low[nxt]);
			if (is_bridge(src, nxt))
				bridge.emplace_back(src, nxt);
		}
	}

	void fill_component(int src) {
		comps[id[src]].push_back(src);
		for (int nxt : adj[src]) {
			if (id[nxt] != -1 || is_bridge(nxt, src))
				continue;
			id[nxt] = id[src];
			fill_component(nxt);
		}
	}

	void add_component(int src) {
		if (id[src] != -1)
			return;
		id[src] = num_comps++;
		comps.emplace_back();
		fill_component(src);
	}
	
	int build() {
		for (int i = 0; i < n; i++) 
			if (ord[i] == -1)
				dfs(i, -1);
		for (int i = 0; i < n; i++) 
			add_component(i);
		tree.resize(num_comps);
		for (auto& b : bridge) {
			int u = id[b.first];
			int v = id[b.second];
			tree[u].push_back(v);
			tree[v].push_back(u);            
		}
		return num_comps;
	}
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(0);
	int n, m; 
	cin >> n >> m;
	TwoEdgeCC B; B.init(n);
	for (int i = 0; i < m ;i++) {
		int u, v; cin >> u >> v;
		B.ae(u, v);
	}
	B.build();
	cout << B.num_comps << '\n';
	for (int i = 0; i < B.num_comps; i++) {
		cout << (int)B.comps[i].size() << " ";
		for (int v : B.comps[i]) 
			cout << v << " ";
		cout << '\n';
	}
}