test/low_link_bridge.test.cpp

test/low_link_bridge.test.cpp · GitHub で見る

依存ライブラリ

コード

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#include "../graph/low_link.hpp"
#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	LowLink g(n);
	for (int repeat_index = 0; repeat_index < m; ++repeat_index) {
		int u, v;
		cin >> u >> v;
		g.add_edge(u, v);
	}
	g.build();
	vector<pair<int, int>> answer;
	for (int id : g.bridges) {
		auto [u, v] = g.edges[id];
		answer.emplace_back(min(u, v), max(u, v));
	}
	sort(answer.begin(), answer.end());
	for (auto [u, v] : answer) cout << u << ' ' << v << '\n';
}

#line 1 "test/low_link_bridge.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B"
#line 1 "graph/low_link.hpp"



#line 1 "components/undirected_csr.hpp"



#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

namespace undirected_csr_detail {
template <class Arc>
void build(int n, std::span<const std::pair<int, int>> edges, std::vector<int>& start, std::unique_ptr<Arc[]>& adj) {
	assert(0 <= n && n < std::numeric_limits<int>::max());
	assert(edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
	start.assign(std::size_t(n) + 1, 0);
	for (auto [u, v] : edges) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		++start[u + 1], ++start[v + 1];
	}
	for (int v = 0; v < n; ++v) start[v + 1] += start[v];
	adj.reset(new Arc[2 * edges.size()]);
	std::vector<int> cursor(start.begin(), start.end() - 1);
	for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
		auto [u, v] = edges[i];
		if constexpr (std::is_same_v<Arc, int>) adj[cursor[u]++] = v, adj[cursor[v]++] = u;
		else adj[cursor[u]++] = {v, i}, adj[cursor[v]++] = {u, i};
	}
}
}

struct UndirectedCSR {
	struct Arc { int to, id; };
	int n;
	std::vector<int> start;
	std::unique_ptr<Arc[]> adj;
	UndirectedCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const Arc> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};

struct UndirectedVertexCSR {
	int n;
	std::vector<int> start;
	std::unique_ptr<int[]> adj;
	UndirectedVertexCSR(int n, std::span<const std::pair<int, int>> edges) : n(n) {
		undirected_csr_detail::build(n, edges, start, adj);
	}
	std::span<const int> operator[](int v) const {
		assert(0 <= v && v < n);
		return {adj.get() + start[v], std::size_t(start[v + 1] - start[v])};
	}
};


#line 5 "graph/low_link.hpp"
#include <algorithm>
#line 8 "graph/low_link.hpp"
#include <cstdint>
#line 13 "graph/low_link.hpp"

struct LowLink {
	using Arc = UndirectedCSR::Arc;
	struct Frame {
		int v, parent, next;
	};
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> ord, low, articulation, bridges;
	explicit LowLink(int n) : n(n) { assert(n >= 0); }
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		assert(edges.size() < std::size_t(std::numeric_limits<int>::max() / 2));
		int id = static_cast<int>(edges.size());
		edges.emplace_back(u, v);
		return id;
	}
	void build() {
		assert(n >= 0 && edges.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		UndirectedCSR graph(n, edges);
		const auto &start = graph.start;
		const auto &adj = graph.adj;
		ord.assign(n, -1);
		low.assign(n, -1);
		articulation.clear();
		bridges.clear();
		std::vector<std::uint8_t> cut(n);
		std::vector<Frame> stack;
		stack.reserve(n);
		int timer = 0;
		for (int root = 0; root < n; ++root) {
			if (ord[root] != -1) continue;
			int children = 0;
			ord[root] = low[root] = timer++;
			stack.push_back({root, -1, start[root]});
			while (!stack.empty()) {
				auto &f = stack.back();
				int v = f.v;
				if (f.next == start[v + 1]) {
					int id = f.parent;
					stack.pop_back();
					if (stack.empty()) cut[v] = children > 1;
					else {
						int p = stack.back().v;
						low[p] = std::min(low[p], low[v]);
						if (ord[p] < low[v]) bridges.push_back(id);
						if (p != root && ord[p] <= low[v]) cut[p] = 1;
					}
					continue;
				}
				auto [to, id] = adj[f.next++];
				if (id == f.parent) continue;
				if (ord[to] != -1) {
					low[v] = std::min(low[v], ord[to]);
					continue;
				}
				children += v == root;
				ord[to] = low[to] = timer++;
				stack.push_back({to, id, start[to]});
			}
		}
		for (int v = 0; v < n; ++v)
			if (cut[v]) articulation.push_back(v);
	}
	bool is_bridge(int id) const {
		assert(0 <= id && id < static_cast<int>(edges.size()) && static_cast<int>(ord.size()) == n);
		auto [u, v] = edges[id];
		if (ord[u] > ord[v]) std::swap(u, v);
		return ord[u] < low[v];
	}
};


#line 4 "test/low_link_bridge.test.cpp"
#include <iostream>
#include <tuple>
#line 8 "test/low_link_bridge.test.cpp"

using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	LowLink g(n);
	for (int repeat_index = 0; repeat_index < m; ++repeat_index) {
		int u, v;
		cin >> u >> v;
		g.add_edge(u, v);
	}
	g.build();
	vector<pair<int, int>> answer;
	for (int id : g.bridges) {
		auto [u, v] = g.edges[id];
		answer.emplace_back(min(u, v), max(u, v));
	}
	sort(answer.begin(), answer.end());
	for (auto [u, v] : answer) cout << u << ' ' << v << '\n';
}