Submission #1342582

#TimeUsernameProblemLanguageResultExecution timeMemory
1342582goats_9Pipes (CEOI15_pipes)C++20
80 / 100
683 ms16760 KiB
/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class DSU {
	int n;
	vector<int> p, rank;

public:
	DSU (int _n) : n(_n), p(n), rank(n) { iota(p.begin(), p.end(), 0); }
	int get(int i) { return (p[i] == i) ? p[i] : (p[i] = get(p[i])); }
	bool unite(int i, int j) {
		i = get(i), j = get(j);
		if (i == j) return false;
		if (rank[i] < rank[j]) swap(i, j);
		if (rank[i] == rank[j]) ++rank[i];
		p[j] = i;
		return true;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	DSU dsu(n), dsu2(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (dsu.unite(--u, --v) || dsu2.unite(u, v)) {
			g[u].push_back(v);
			g[v].push_back(u);
		}
	}
	vector<int> num(n, -1), low(n, -1);
	vector<pair<int, int>> a;
	int timer = 0;
	auto dfs = [&] (auto&& self, int u, int p) -> void {
		num[u] = low[u] = timer++;
		bool par = false;;
		for (int v : g[u]) {
			if (v == p && !par) {
				par = true;
				continue;
			}
			if (num[v] == -1) {
				 self(self, v, u);
				 low[u] = min(low[u], low[v]);
				 if (low[v] > num[u]) a.emplace_back(u + 1, v + 1);
			} else low[u] = min(low[u], num[v]);
		}
	};
	for (int i = 0; i < n; i++) if (num[i] == -1) dfs(dfs, i, -1);
	for (auto [x, y] : a) cout << x << ' ' << y << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...