library/graphs/block-cut-tree.hpp

• View this file on GitHub
• Last update: 2022-07-23 18:16:07-04:00
• Include: #include "library/graphs/block-cut-tree.hpp"

Depends on

• library/graphs/biconnected-components.hpp
• library/graphs/low-link.hpp

Verified with

• verify/yukicoder/yukicoder-1326.test.cpp

Code

#pragma once

#include "biconnected-components.hpp"

template <typename G>
struct BlockCutTree {
	const G& g;
	BiConnectedComponents<G> bcc;
	std::vector<std::vector<int>> aux;
	std::vector<int> idar, idcc;

	BlockCutTree(const G& _g) : g(_g), bcc(g) { build(); }

	void build() {
		auto ar = bcc.articulation;
		idar.resize(g.size(), -1);
		idcc.resize(g.size(), -1);
		for (int i = 0; i < (int)ar.size(); i++) idar[ar[i]] = i;

		aux.resize(ar.size() + bcc.bc.size());
		std::vector<int> last(g.size(), -1);
		for (int i = 0; i < (int)bcc.bc.size(); i++) {
			std::vector<int> st;
			for (auto& [u, v] : bcc.bc[i]) st.push_back(u), st.push_back(v);
			for (auto& u : st) {
				if (idar[u] == -1)
					idcc[u] = i + (int)ar.size();
				else if (last[u] != i) {
					add(i + (int)ar.size(), idar[u]);
					last[u] = i;
				}
			}
		}
	}

	std::vector<int>& operator[](int i) { return aux[i]; }

	int size() const { return (int)aux.size(); }

	int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; }

	bool is_arti(int i) { return idar[i] != -1; }

	int arti() const { return bcc.articulation.size(); }

private:
	void add(int i, int j) {
		if (i == -1 or j == -1) return;
		aux[i].push_back(j);
		aux[j].push_back(i);
	};
};

template <typename G>
struct LowLink {
	int N;
	const G& g;
	std::vector<int> ord, low, articulation;
	std::vector<std::pair<int, int>> bridge;

	LowLink(const G& _g) : g(_g) {
		N = (int)g.size();
		ord.resize(N, -1);
		low.resize(N, -1);
		int k = 0;
		for (int i = 0; i < N; i++)
			if (ord[i] == -1) k = dfs(i, k, -1);
	}

	int dfs(int idx, int k, int par) {
		low[idx] = (ord[idx] = k++);
		int cnt = 0;
		bool is_arti = false, flg = false;
		for (auto &to : g[idx]) {
			if (ord[to] == -1) {
				cnt++;
				k = dfs(to, k, idx);
				low[idx] = std::min(low[idx], low[to]);
				is_arti |= (par != -1) && (low[to] >= ord[idx]);
				if (ord[idx] < low[to]) {
					bridge.emplace_back(std::minmax(idx, (int)to));
				}
			} else if (to != par || std::exchange(flg, true)) {
				low[idx] = std::min(low[idx], ord[to]);
			}
		}
		is_arti |= par == -1 && cnt > 1;
		if (is_arti) articulation.push_back(idx);
		return k;
	}
};

template <typename G>
struct BiConnectedComponents : LowLink<G> {
	using LL = LowLink<G>;

	std::vector<int> used;
	std::vector<std::vector<std::pair<int, int>>> bc; // will not include BCC's of size 1!
	std::vector<std::pair<int, int>> tmp;

	BiConnectedComponents(const G& _g) : LL(_g) { build(); }

	void build() {
		used.assign(this->g.size(), 0);
		for (int i = 0; i < (int)used.size(); i++) {
			if (!used[i]) dfs(i, -1);
		}
	}

	void dfs(int idx, int par) {
		used[idx] = true;
		for (auto& to : this->g[idx]) {
			if (to == par) continue;
			if (!used[to] || this->ord[to] < this->ord[idx]) {
				tmp.emplace_back(std::minmax(idx, to));
			}
			if (!used[to]) {
				dfs(to, idx);
				if (this->low[to] >= this->ord[idx]) {
					bc.emplace_back();
					while (true) {
						auto e = tmp.back();
						bc.back().emplace_back(e);
						tmp.pop_back();
						if (e.first == std::min(idx, to) && e.second == std::max(idx, to)) {
							break;
						}
					}
				}
			}
		}
	}
};

template <typename G>
struct BlockCutTree {
	const G& g;
	BiConnectedComponents<G> bcc;
	std::vector<std::vector<int>> aux;
	std::vector<int> idar, idcc;

	BlockCutTree(const G& _g) : g(_g), bcc(g) { build(); }

	void build() {
		auto ar = bcc.articulation;
		idar.resize(g.size(), -1);
		idcc.resize(g.size(), -1);
		for (int i = 0; i < (int)ar.size(); i++) idar[ar[i]] = i;

		aux.resize(ar.size() + bcc.bc.size());
		std::vector<int> last(g.size(), -1);
		for (int i = 0; i < (int)bcc.bc.size(); i++) {
			std::vector<int> st;
			for (auto& [u, v] : bcc.bc[i]) st.push_back(u), st.push_back(v);
			for (auto& u : st) {
				if (idar[u] == -1)
					idcc[u] = i + (int)ar.size();
				else if (last[u] != i) {
					add(i + (int)ar.size(), idar[u]);
					last[u] = i;
				}
			}
		}
	}

	std::vector<int>& operator[](int i) { return aux[i]; }

	int size() const { return (int)aux.size(); }

	int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; }

	bool is_arti(int i) { return idar[i] != -1; }

	int arti() const { return bcc.articulation.size(); }

private:
	void add(int i, int j) {
		if (i == -1 or j == -1) return;
		aux[i].push_back(j);
		aux[j].push_back(i);
	};
};

Back to top page