verify/yukicoder/yukicoder-1326.test.cpp

• View this file on GitHub
• Last update: 2022-07-23 18:28:05-04:00
• Problem: https://yukicoder.me/problems/no/1326

Depends on

• library/graphs/biconnected-components.hpp
• library/graphs/block-cut-tree.hpp
• LCA Jump (library/graphs/lca-jump.hpp)
• library/graphs/low-link.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1326"

#include <bits/stdc++.h>
#include "../../library/graphs/block-cut-tree.hpp"
#include "../../library/graphs/lca-jump.hpp"

int main() {
	using namespace std;
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	BlockCutTree bct(g);
	g = bct.aux;
	LCAJump lca;
	int sz = (int)g.size();
	lca.init(sz);
	for (int u = 0; u < sz; ++u) {
		for (int v : g[u]) {
			if (u < v) {
				lca.ae(u, v);
			}
		}
	}
	lca.gen(0);
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		if (u == v) {
			cout << 0 << '\n';
			continue;	
		}
		int ans = lca.depth[bct.id(u)];
		ans += lca.depth[bct.id(v)];
		ans -= lca.depth[lca.lca(bct.id(u), bct.id(v))] * 2;
		ans -= bct.is_arti(u);
		ans -= bct.is_arti(v);
		ans /= 2;
		cout << ans << '\n';
	}
	return 0;
}

#define PROBLEM "https://yukicoder.me/problems/no/1326"

#include <bits/stdc++.h>



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);
	};
};

struct LCAJump {
	int n;
	std::vector<std::vector<int>> par;
	std::vector<std::vector<int>> adj;
	std::vector<int> depth;

	void init(int _n) {
		n = _n;
		int d = 1;
		while ((1 << d) < n) d++;
		par.assign(d, std::vector<int>(n));
		adj.resize(n);
		depth.resize(n);
	}

	void ae(int x, int y) {
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	void gen(int root = 0) {
		par[0][root] = root;
		dfs(root);
	}

	void dfs(int src = 0) {
		for (int i = 1; i < (int)par.size(); i++) {
			par[i][src] = par[i - 1][par[i - 1][src]];
		}
		for (int nxt : adj[src]) {
			if (nxt == par[0][src]) continue;
			depth[nxt] = depth[par[0][nxt] = src] + 1;
			dfs(nxt);
		}
	}

	int jump(int x, int d) {
		for (int i = 0; i < (int)par.size(); i++) {
			if ((d >> i) & 1) {
				x = par[i][x];
			}
		}
		return x;
	}
	
	int lca(int x, int y) {
		if (depth[x] < depth[y]) std::swap(x, y);
		x = jump(x, depth[x] - depth[y]);
		if (x == y) return x;
		for (int i = (int)par.size() - 1; i >= 0; i--) {
			int nx = par[i][x];
			int ny = par[i][y];
			if (nx != ny) x = nx, y = ny;
		}
		return par[0][x];
	}
};

int main() {
	using namespace std;
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	BlockCutTree bct(g);
	g = bct.aux;
	LCAJump lca;
	int sz = (int)g.size();
	lca.init(sz);
	for (int u = 0; u < sz; ++u) {
		for (int v : g[u]) {
			if (u < v) {
				lca.ae(u, v);
			}
		}
	}
	lca.gen(0);
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		if (u == v) {
			cout << 0 << '\n';
			continue;	
		}
		int ans = lca.depth[bct.id(u)];
		ans += lca.depth[bct.id(v)];
		ans -= lca.depth[lca.lca(bct.id(u), bct.id(v))] * 2;
		ans -= bct.is_arti(u);
		ans -= bct.is_arti(v);
		ans /= 2;
		cout << ans << '\n';
	}
	return 0;
}

Back to top page