#include <iostream> #include <set> #include <algorithm> #include <math.h> #include <vector> #include <map> #include <unordered_map> #include <unordered_set> #include <iterator> // #include<bits/stdc++.h> using namespace std; #define forn(i, a, n) for (int i = a; i < n; i++) #define MAXN 1000000 #define MOD 1000000007 #define int long long #define tc \ int t; \ cin >> t; \ while (t--) #define TC size(arr) / size(arr[0]) #define mp make_pair #define Radhe ios::sync_with_stdio(false); #define Krishna cin.tie(NULL); int Time = 0; vector<pair<int, int>> br; set<pair<int, int>> res; vector<int> low, disc; vector<vector<int>> adj; void dfsBR(int u, int p) { low[u] = disc[u] = ++Time; for (int &v : adj[u]) { if (v == p) continue; // we don't want to go back through the same path. // if we go back is because we found another way back if (!disc[v]) { res.insert({u, v}); // if V has not been discovered before dfsBR(v, u); // recursive DFS call if (disc[u] < low[v]) // condition to find a bridge br.push_back({u, v}); low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u } else // if v was already discovered means that we found an ancestor { if (low[u] >= disc[v]) { low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time res.insert({u, v}); }else{ if(res.find({v,u})==res.end()){ res.insert({u,v}); } } } } } void BR() { low = disc = vector<int>(adj.size(), 0); Time = 0; for (int u = 0; u < adj.size(); u++) { if (!disc[u]) { dfsBR(u, u); } } } void solve() { int n, m; cin >> n >> m; adj.resize(n); forn(i, 0, m) { int u, v; cin >> u >> v; u--, v--; adj[u].push_back(v); adj[v].push_back(u); } BR(); if (br.size()) { cout << 0 << endl; return; } // cout<<br.size()<<endl; for (auto &x : res) { cout << x.first + 1 << " " << x.second + 1 << endl; } } int32_t main() { Radhe Krishna { solve(); } return 0; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter