Graph Ordering

input/code.cpp: In function 'std::tuple<std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >, std::vector<int, std::allocator<int> >, int> blockCutTrees(const std::vector<std::array<int, 2> >&, int)':
input/code.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i = 0; i < edges.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(vector<bool>::reference b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename T = typename A::value_type>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
using ll = long long;
using ld = long double;
pair<vector<int>, int> getBiconnv(const vector<array<int, 2>>& edges, int n) {
	assert(n > 0);
	int m = edges.size();
	vector<vector<int>> E(n);
	for (auto& e : edges) {
		assert(e[0] != e[1]);
		E[e[0]].push_back(e[1]);
		E[e[1]].push_back(e[0]);
	}
	vector<int> low(n, -1), H(n), pv(n, -1), order;
	int numComps = 0;
	for (int i = 0; i < n; ++i) {
		if (low[i] != -1) continue;
		bool isolated = true;
		function<void(int)> dfs = [&](int x) {
			order.push_back(x);
			low[x] = H[x];
			for (int y : E[x]) {
				if (low[y] == -1) {
					isolated = false;
					H[y] = H[x] + 1;
					pv[y] = x;
					dfs(y);
					low[x] = min(low[x], low[y]);
				} else if (H[y] < H[x] - 1) {
					// xy is a backedge.
					low[x] = min(low[x], H[y]);
				}
			}
		};
		dfs(i);
		if (isolated) numComps++; // Isolated vertex forms a block on its own.
	}
	vector<int> vcomp(n, -1), ecomp(m); // block of parent-edge, block of edge
	for (int x : order) {
		if (pv[x] == -1) continue;
		if (low[x] >= H[pv[x]]) vcomp[x] = numComps++;
		else vcomp[x] = vcomp[pv[x]];
	}
	for (int i = 0; i < m; ++i) {
		auto& e = edges[i];
		int deeper = H[e[0]] > H[e[1]] ? e[0] : e[1];
		ecomp[i] = vcomp[deeper];
	}
	return {ecomp, numComps};
}
tuple<vector<vector<int>>, vector<int>, int> blockCutTrees(const vector<array<int, 2>>& edges, int n) {
	auto [eblock, numBlocks] = getBiconnv(edges, n);
	vector<vector<int>> vblocks(n); // blocks v is contained in
	for (int i = 0; i < edges.size(); ++i) {
		vblocks[edges[i][0]].push_back(eblock[i]);
		vblocks[edges[i][1]].push_back(eblock[i]);
	}
	vector<vector<int>> adj(numBlocks);
	vector<int> treeId(n);
	for (int v = 0, blockId = 0; v < n; ++v)
		if (vblocks[v].empty()) treeId[v] = blockId++;
	for (int v = 0; v < n; ++v) {
		if (vblocks[v].empty()) continue;
		sort(vblocks[v].begin(), vblocks[v].end());
		vblocks[v].erase(unique(vblocks[v].begin(), vblocks[v].end()), vblocks[v].end());
		if (vblocks[v].size() > 1) {
			// Cut vertex.
			int cutId = adj.size();
			treeId[v] = cutId;
			adj.emplace_back();
			for (int blockId : vblocks[v]) {
				adj[cutId].push_back(blockId);
				adj[blockId].push_back(cutId);
			}
		} else {
			// Vertex is in a single block.
			treeId[v] = vblocks[v][0];
		}
	}
	return {adj, treeId, numBlocks};
}
struct BipolarOrientation {
	vector<vector<int>> E;
	vector<array<int, 2>> edges;
	// Do not rely on following intermediate variables publicly!
	vector<int> depth, low;
	vector<bool> vis, isBefore;
	vector<list<int>::iterator> vpos;
	list<int> ordering;
	BipolarOrientation(int n) : E(n), depth(n), low(n), vis(n), isBefore(n), vpos(n) {}
	void addEdge(int u, int v) {
		E[u].push_back(v);
		E[v].push_back(u);
		edges.push_back({u, v});
	}
	void dfs(int x) {
		low[x] = x;
		for (auto y : E[x]) {
			if (depth[y] == -1) {
				depth[y] = depth[x] + 1;
				dfs(y);
				if (depth[low[y]] < depth[low[x]]) low[x] = low[y];
			} else if (depth[y] < depth[x] - 1) {
				// This is a backedge that is not to the parent
				if (depth[y] < depth[low[x]]) low[x] = y;
			}
		}
	}
	void dfsOrder(int x, int p = -1) {
		vis[x] = true;
		if (p != -1) {
			assert(low[x] != x);
			if (isBefore[low[x]]) {
				vpos[x] = ordering.insert(vpos[p], x);
			} else {
				vpos[x] = ordering.insert(next(vpos[p]), x);
			}
			// Update isBefore for relation (parent[x], x)
			isBefore[p] = !isBefore[low[x]];
		}
		for (auto y : E[x])
			if (!vis[y]) dfsOrder(y, x);
	}
	/* Assumes non-empty graph has a bipolar orientation for s, t:
	for n >= 2, graph after adding edge st is 2-vertex-connected.
	Returns st-numbering in O(n+m): {s,...,t}. Can be run multiple times per BipolarOrientation instance. */
	vector<int> getOrdering(int s, int t) {
		int n = E.size();
		assert(0 <= s && s < n && 0 <= t && t < n);
		if (n == 1) return {s};
		assert(s != t);
		if (n == 2) return {s, t};
		fill(depth.begin(), depth.end(), -1);
		fill(vis.begin(), vis.end(), false);
		ordering.clear();
		depth[s] = 0;
		// Make sure t is first neighbor of s
		E[s].insert(E[s].begin(), t);
		E[t].push_back(s);
		dfs(s);
		isBefore[s] = false;
		vpos[s] = ordering.insert(ordering.end(), s);
		dfsOrder(s);
		E[s].erase(E[s].begin());
		E[t].pop_back();
		return vector<int>(ordering.begin(), ordering.end());
	}
	/* Returns st-numbering for non-empty graph if there is s,t that works, else return {}.
	List will have size n: {s,...,t}. Can be run multiple times per BipolarOrientation instance. O(n + m log m). */
	vector<int> getOrdering() {
		int n = E.size();
		assert(n > 0);
		if (n == 1) return getOrdering(0, 0);
		auto [bcAdj, bcId, numBlocks] = blockCutTrees(edges, n);
		// Graph is biconnected, so any s,t works.
		if (numBlocks == 1) return getOrdering(0, 1);
		// There should be one non-trivial block-cut tree that is a line; s,t must belong to the blocks at two ends.
		vector<int> ends;
		bool hasDeg0 = false;
		for (int i = 0; i < numBlocks; ++i) {
			if (bcAdj[i].size() == 1) ends.push_back(i);
			else if (bcAdj[i].empty()) hasDeg0 = true;
		}
		if (hasDeg0 || ends.size() != 2) return {};
		int s = find(bcId.begin(), bcId.end(), ends[0]) - bcId.begin();
		int t = find(bcId.begin(), bcId.end(), ends[1]) - bcId.begin();
		return getOrdering(s, t);
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	BipolarOrientation g(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		g.addEdge(a, b);
	}
	auto order = g.getOrdering(); // or g.getOrdering(s, t) for fixed s,t
	if (order.empty()) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	for (int x : order) cout << x + 1 << " \n"[x == *order.rbegin()];
}

Test 1

Group: 1, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 5

Verdict: ACCEPTED

Test 3

Group: 1, 5

Verdict: ACCEPTED

Test 4

Group: 1, 5

Verdict: ACCEPTED

Test 5

Group: 1, 5

Verdict: ACCEPTED

Test 6

Group: 2, 3, 5

Verdict: ACCEPTED

Test 7

Group: 2, 3, 5

Verdict: ACCEPTED

Test 8

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 9

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 2, 3, 5

Verdict: ACCEPTED

Test 12

Group: 2, 3, 5

Verdict: ACCEPTED

Test 13

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 14

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 15

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 16

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 17

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 18

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 19

Group: 3, 4, 5

Verdict: ACCEPTED

Test 20

Group: 3, 4, 5

Verdict: ACCEPTED

Test 21

Group: 3, 4, 5

Verdict: ACCEPTED

Test 22

Group: 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 3, 5

Verdict: ACCEPTED

Test 24

Group: 3, 5

Verdict: ACCEPTED

Test 25

Group: 3, 5

Verdict: ACCEPTED

Test 26

Group: 3, 5

Verdict: ACCEPTED

Test 27

Group: 3, 5

Verdict: ACCEPTED

Test 28

Group: 5

Verdict: ACCEPTED

Test 29

Group: 5

Verdict: ACCEPTED

Test 30

Group: 4, 5

Verdict: ACCEPTED

Test 31

Group: 4, 5

Verdict: ACCEPTED

Test 32

Group: 4, 5

Verdict: ACCEPTED

Test 33

Group: 4, 5

Verdict: ACCEPTED

Test 34

Group: 5

Verdict: ACCEPTED

Test 35

Group: 5

Verdict: ACCEPTED

Test 36

Group: 5

Verdict: ACCEPTED

Test 37

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 38

Group: 2, 3, 5

Verdict: ACCEPTED

Test 39

Group: 2, 3, 5

Verdict: ACCEPTED

Test 40

Group: 2, 3, 5

Verdict: ACCEPTED

Test 41

Group: 1, 2, 3, 5

Verdict: ACCEPTED

Test 42

Group: 2, 3, 5

Verdict: ACCEPTED

Test 43

Group: 3, 4, 5

Verdict: ACCEPTED

Test 44

Group: 3, 4, 5

Verdict: ACCEPTED

Test 45

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 46

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 47

Group: 2, 3, 5

Verdict: ACCEPTED

Test 48

Group: 3, 4, 5

Verdict: ACCEPTED

Test 49

Group: 4, 5

Verdict: ACCEPTED