Light rail connections

#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int N = 10100;
 
int n, m;
vector<pair<int, int>> g[N];
bool seen_as_bridge[N];
 
void components(int banned_edge) {
	vi depth(n, -1);
	vi mindepth(n, -1);
	auto dfs = [&](auto self, int u, int p) -> void {
		depth[u] = depth[p] + 1;
		mindepth[u] = depth[u];
		for (auto [v, ei] : g[u]) {
			if (ei == banned_edge) {
				continue;
			}
			if (depth[v] != -1) {
				// edge goes up
				mindepth[u] = min(depth[v], mindepth[u]);
			} else {
				if (mindepth[v] >= depth[v]) {
					seen_as_bridge[ei] = 1;
				}
				self(self, v, u);
				mindepth[u] = min(mindepth[v], mindepth[u]);
			}
		}
	};
	for (int i = 0; i < n; ++i) {
		if (depth[i] != -1) continue;
		dfs(dfs, i, i);
	}
}
 
struct UF {
	vi p;
	UF(int n) : p(n, -1) {
	}
	int find(int u) {
		while (p[u] >= 0) u = p[u];
		return u;
	}
	int same(int a, int b) {
		a = find(a);
		b = find(b);
		return a == b;
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (-p[a] > -p[b]) {
			p[a] += p[b];
			p[b] = a;
		} else {
			p[b] += p[a];
			p[a] = b;
		}
	}
};
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
 
	cin >> n >> m;
 
	vector<pii> edges;
 
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
		edges.push_back({a, b});
	}
 
	vi vis(n);
	vi seen;
	auto dfs = [&](auto self, int i) -> void {
		if (vis[i]) return;
		vis[i] = 1;
		seen.push_back(i);
		for (auto [j, ei] : g[i]) {
			if (seen_as_bridge[ei]) continue;
			self(self, j);
		}
	};
 
	UF oneuf(n);
 
	vector<vi> ones;
	vis = vi(n, 0);
	for (int i = 0; i < n; ++i) {
		if (vis[i]) continue;
		seen.clear();
		dfs(dfs, i);
		ones.push_back(seen);
		for (int j = 0; j + 1 < (int)seen.size(); ++j) {
			oneuf.unite(seen[j], seen[j + 1]);
		}
	}
 
	components(-1);
 
	for (int i = 0; i < m; ++i) {
		components(i);
	}
 
	UF twouf(n);
 
	vector<vi> twos;
	vis = vi(n, 0);
	for (int i = 0; i < n; ++i) {
		if (vis[i]) continue;
		seen.clear();
		dfs(dfs, i);
		twos.push_back(seen);
		for (int j = 0; j + 1 < (int)seen.size(); ++j) {
			twouf.unite(seen[j], seen[j + 1]);
		}
	}
 
 
	UF uf1(n), uf2(n), uf3(n);
	vector<pii> ans;
	for (auto [a, b] : edges) {
		if (!uf1.same(a, b)) {
			ans.emplace_back(a, b);
			uf1.unite(a, b);
		} else if (!uf2.same(a, b)) {
			ans.emplace_back(a, b);
			uf2.unite(a, b);
		}else if (!uf3.same(a, b)) {
			ans.emplace_back(a, b);
			uf3.unite(a, b);
		}
	}
 
	cout << ans.size() << endl;
	for (auto [a, b] : ans) cout << a+1 << ' ' << b+1 << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED