fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. using namespace std;
  4. const int MAXN = 100000;
  5. multiset<int> g[MAXN+1];
  6. typedef pair<int,int> pii;
  7. bool vis[MAXN+1];
  8.  
  9. void dfs(int v)
  10. {
  11. 	vis[v] = true;
  12. 	for(auto it = g[v].begin();it != g[v].end();++it)
  13. 	{
  14. 		if(!vis[*it])
  15. 		{
  16. 			dfs(*it);
  17. 		}
  18. 	}
  19. }
  20. stack<int> cycle;
  21. void euler_dfs(int v)
  22. {
  23. 	stack<int> nodes;
  24. 	int location = v;
  25. 	//nodes.push(location);
  26. 	do
  27. 	{
  28. 		if(!g[location].empty())
  29. 		{
  30. 			int v = *g[location].begin();
  31. 			g[location].erase(g[location].begin());
  32. 			g[v].erase(g[v].find(location));
  33. 			nodes.push(location);
  34. 			location = v;
  35. 		}else{
  36. 			while(g[location].empty())
  37. 			{
  38. 				cycle.push(location);
  39. 				if(nodes.empty())
  40. 					break;
  41. 				location = nodes.top();
  42. 				nodes.pop();
  43. 			}
  44. 		}	
  45. 	}while(!nodes.empty());
  46.  
  47. 	while(!cycle.empty())
  48. 	{
  49. 		int tp = cycle.top();
  50. 		cycle.pop();
  51. 		if(!cycle.empty())
  52. 		{
  53. 			cout << tp << ' ' << cycle.top() << '\n';
  54. 		}
  55. 	}
  56.  
  57. }
  58.  
  59. int main()
  60. {
  61. 	int N,M;
  62. 	cin >> N >> M;
  63. 	for(int i = 0;i < M;++i)
  64. 	{
  65. 		int x,y;
  66. 		cin >> x >> y;
  67. 		g[x].insert(y);
  68. 		g[y].insert(x);
  69. 	}
  70. 	//check all have even degrees
  71. 	for(int i = 1;i <= N;++i)
  72. 	{
  73. 		if(g[i].size()%2 != 0 || g[i].size() == 0)
  74. 		{
  75. 			cout << "NO\n";
  76. 			return 0;
  77. 		}
  78. 	}
  79.  
  80. 	//check for connected : dfs and all are visited #Simple
  81.  
  82. 	dfs(1);
  83. 	for(int i = 1;i <= N;++i)
  84. 	{
  85. 		if(!vis[i])
  86. 		{
  87. 			cout << "NO\n";
  88. 			return 0;
  89. 		}
  90. 	}
  91. 	//print the eulerian circuit
  92. 	cout << "YES\n";
  93. 	euler_dfs(1);
  94.  
  95. 	return 0;
  96. }
  97.  
Runtime error #stdin #stdout 0s 5912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mRFsbv
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!