fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <pthread.h>
  3. #define ll long long
  4. #define deb(x) cout << #x << " : " << x << endl;
  5. #define take_input(a)                                                          \
  6.   for (auto &x : a)                                                            \
  7.     cin >> x;
  8. #define _output(a)                                                             \
  9.   for (auto &x : a)                                                            \
  10.     cout << x << " ";                                                          \
  11.   cout << endl;
  12. #define srt(a) sort(a.begin(), a.end())
  13. #define nl "\n"
  14. using namespace std;
  15.  
  16. class Graph {
  17. private:
  18.   int V;
  19.   list<int> *adj;
  20.   bool *visited;
  21.   int *tin;
  22.   int *low;
  23.   int timer = 1;
  24.   map<pair<int, int>, int> ans;
  25.  
  26. public:
  27.   bool isPossible = true;
  28.   Graph(int n);
  29.   void addEdge(int u, int v);
  30.   void dfs(int node, int parent);
  31.   void printSol();
  32. };
  33.  
  34. Graph::Graph(int n) {
  35.   V = n + 1;
  36.   adj = new list<int>[V];
  37.   visited = new bool[V];
  38.   tin = new int[V];
  39.   low = new int[V];
  40. }
  41.  
  42. void Graph::addEdge(int u, int v) {
  43.   adj[u].push_back(v);
  44.   adj[v].push_back(u);
  45. }
  46.  
  47. void Graph::dfs(int node, int parent) {
  48.   if (!isPossible)
  49.     return;
  50.   visited[node] = true;
  51.   tin[node] = timer;
  52.   low[node] = timer;
  53.   timer++;
  54.  
  55.   for (auto v : adj[node]) {
  56.     if (v == parent)
  57.       continue;
  58.  
  59.     if (ans.find({node, v}) == ans.end() && ans.find({v, node}) == ans.end())
  60.       ans[{node, v}] = true;
  61.  
  62.     if (!visited[v]) {
  63.       dfs(v, node);
  64.  
  65.       low[node] = min(low[node], low[v]);
  66.       if (tin[node] < low[v]) {
  67.         isPossible = false;
  68.         return;
  69.       }
  70.  
  71.     } else {
  72.       low[node] = min(low[node], low[v]);
  73.     }
  74.   }
  75. }
  76.  
  77. void Graph::printSol() {
  78.   for (auto i : ans) {
  79.     cout << i.first.first << " " << i.first.second << nl;
  80.   }
  81. }
  82.  
  83. int main() {
  84.   ios_base::sync_with_stdio(false);
  85.   cin.tie(NULL);
  86.   int T = 1;
  87.   // cin >> T;
  88.  
  89.   while (T--) {
  90.     int n, m;
  91.     cin >> n >> m;
  92.     Graph g(n);
  93.  
  94.     for (int i = 0; i < m; i++) {
  95.       int u, v;
  96.       cin >> u >> v;
  97.       g.addEdge(u, v);
  98.     }
  99.  
  100.     g.dfs(1, 1);
  101.  
  102.     if (g.isPossible)
  103.       g.printSol();
  104.     else
  105.       cout << 0 << nl;
  106.   }
  107.  
  108.   return 0;
  109. }
  110.  
Success #stdin #stdout 0s 5252KB
comments (?)
stdin
copy 
6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5
stdout
copy 
1 2
2 3
3 1
3 5
4 2
4 6
5 4
6 5
https://ideone.com/Pn4Wdh
language:
C++ (gcc 8.3)
created:
54 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!