fork download
  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
stdin
6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5
stdout
1 2
2 3
3 1
3 5
4 2
4 6
5 4
6 5