제출 #1342584

#제출 시각아이디문제언어결과실행 시간메모리
1342584goats_9Pipes (CEOI15_pipes)C++20
100 / 100
655 ms14444 KiB
/* Author: goats_9 */

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

using ll = long long;

class DSU {
	int n;
	vector<int> e;

public:
	DSU (int _n) : n(_n), e(n, -1) {}
	int get(int i) { return (e[i] < 0) ? i : (e[i] = get(e[i])); }
	bool unite(int i, int j) {
		i = get(i), j = get(j);
		if (i == j) return false;
		if (e[i] > e[j]) swap(i, j);
		e[i] += e[j];
		e[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);
	int timer = 0;
	auto dfs = [&] (auto&& self, int u, int p) -> int {
		num[u] = timer++;
		int low = num[u];
		bool par = false;
		for (int v : g[u]) {
			if (v == p && !par) {
				par = true;
				continue;
			}
			if (num[v] == -1) {
				int z = self(self, v, u);
				low = min(low, z);
				if (z > num[u]) cout << u + 1 << ' ' << v + 1 << '\n';
			} else low = min(low, num[v]);
		}
		return low;
	};
	for (int i = 0; i < n; i++) if (num[i] == -1) dfs(dfs, i, -1);
	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...