Submission #1278650

#TimeUsernameProblemLanguageResultExecution timeMemory
1278650g4yuhgPipes (CEOI15_pipes)C++20
70 / 100
692 ms17480 KiB
//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 100005
#define LOG 18
using namespace std;

// y tuong: vi len toi 1e6 canh, ta nhan thay chi can quan tam toi da 2 * n - 2 canh thoi. nhu the dam bao 
// tao du cac tplt manh roi
// ta se dung 2 dsu, 1 dinh duoc noi 2 lan roi thi khong can noi them nua

const ll inf = 1e9;

bool ghuy4g;

ll n, m;
vector<ll> adj[N];
ll num[N], low[N], timeDfs;
vector<ll> par, par1;

vector<pii> g;

ll find(ll u) {
	if (par[u] < 0) return u;
	return par[u] = find(par[u]);
}

void join(ll u, ll v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (par[u] <= par[v]) {
		par[u] += par[v];
		par[v] = u;
	}
	else {
		par[v] += par[u];
		par[u] = v;
	}
}

ll find1(ll u) {
	if (par1[u] < 0) return u;
	return par1[u] = find1(par1[u]);
}

void join1(ll u, ll v) {
	u = find1(u);
	v = find1(v);
	if (u == v) return;
	if (par1[u] <= par1[v]) {
		par1[u] += par1[v];
		par1[v] = u;
	}
	else {
		par1[v] += par1[u];
		par1[u] = v;
	}
}

void dfs(ll u, ll parent) {
	num[u] = low[u] = ++ timeDfs;
	bool see = 0;
	for (auto v : adj[u]) {
		if (v == parent && see == 0) {
			see = 1;
			continue;
		}
		if (num[v]) {
			low[u] = min(low[u], num[v]);
		}
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] == num[v]) {
				cout << u << " " << v << endl;
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= n; i ++) {
		if (num[i] == 0) {
			dfs(i, 0);
		}
	}
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	par.resize(n + 1, -1);
	par1.resize(n + 1, -1);
	for (int i = 1; i <= n; i ++) {
		par[i] = par1[i] = -1;
	}
	for (int i = 1; i <= m; i ++) {
		ll u, v;
		cin >> u >> v;
		if (find(u) != find(v)) {
			join(u, v);
			g.push_back({u, v});
		}
		else if (find1(u) != find1(v)) {
			join1(u, v);
			g.push_back({u, v});
		}
	}
	
	par.clear();
	par1.clear();
	
	while (g.size()) {
		//cout << g.back().fi << " " << g.back().se << endl;
		adj[g.back().fi].push_back(g.back().se);
		adj[g.back().se].push_back(g.back().fi);
		g.pop_back();
	}
	
	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	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...