fork download
copy 
  1. // A C++ program to check if a given graph is Eulerian or not 
  2. #include<iostream> 
  3. #include <list> 
  4. using namespace std; 
  5.  
  6. // A class that represents an undirected graph 
  7. class Graph 
  8. { 
  9. 	int V; // No. of vertices 
  10. 	list<int> *adj; // A dynamic array of adjacency lists 
  11. public: 
  12. 	// Constructor and destructor 
  13. 	Graph(int V) {this->V = V; adj = new list<int>[V]; } 
  14. 	~Graph() { delete [] adj; } // To avoid memory leak 
  15.  
  16. 	// function to add an edge to graph 
  17. 	void addEdge(int v, int w); 
  18.  
  19. 	// Method to check if this graph is Eulerian or not 
  20. 	int isEulerian(); 
  21.  
  22. 	// Method to check if all non-zero degree vertices are connected 
  23. 	bool isConnected(); 
  24.  
  25. 	// Function to do DFS starting from v. Used in isConnected(); 
  26. 	void DFSUtil(int v, bool visited[]); 
  27. }; 
  28.  
  29. void Graph::addEdge(int v, int w) 
  30. { 
  31. 	adj[v].push_back(w); 
  32. 	adj[w].push_back(v); // Note: the graph is undirected 
  33. } 
  34.  
  35. void Graph::DFSUtil(int v, bool visited[]) 
  36. { 
  37. 	// Mark the current node as visited and print it 
  38. 	visited[v] = true; 
  39.  
  40. 	// Recur for all the vertices adjacent to this vertex 
  41. 	list<int>::iterator i; 
  42. 	for (i = adj[v].begin(); i != adj[v].end(); ++i) 
  43. 		if (!visited[*i]) 
  44. 			DFSUtil(*i, visited); 
  45. } 
  46.  
  47. // Method to check if all non-zero degree vertices are connected. 
  48. // It mainly does DFS traversal starting from 
  49. bool Graph::isConnected() 
  50. { 
  51. 	// Mark all the vertices as not visited 
  52. 	bool visited[V]; 
  53. 	int i; 
  54. 	for (i = 0; i < V; i++) 
  55. 		visited[i] = false; 
  56.  
  57. 	// Find a vertex with non-zero degree 
  58. 	for (i = 0; i < V; i++) 
  59. 		if (adj[i].size() != 0) 
  60. 			break; 
  61.  
  62. 	// If there are no edges in the graph, return true 
  63. 	if (i == V) 
  64. 		return true; 
  65.  
  66. 	// Start DFS traversal from a vertex with non-zero degree 
  67. 	DFSUtil(i, visited); 
  68.  
  69. 	// Check if all non-zero degree vertices are visited 
  70. 	for (i = 0; i < V; i++) 
  71. 	if (visited[i] == false && adj[i].size() > 0) 
  72. 			return false; 
  73.  
  74. 	return true; 
  75. } 
  76.  
  77. /* The function returns one of the following values 
  78. 0 --> If grpah is not Eulerian 
  79. 1 --> If graph has an Euler path (Semi-Eulerian) 
  80. 2 --> If graph has an Euler Circuit (Eulerian) */
  81. int Graph::isEulerian() 
  82. { 
  83. 	// Check if all non-zero degree vertices are connected 
  84. 	if (isConnected() == false) 
  85. 		return 0; 
  86.  
  87. 	// Count vertices with odd degree 
  88. 	int odd = 0; 
  89. 	for (int i = 0; i < V; i++) 
  90. 		if (adj[i].size() & 1) 
  91. 			odd++; 
  92.  
  93. 	// If count is more than 2, then graph is not Eulerian 
  94. 	if (odd > 2) 
  95. 		return 0; 
  96.  
  97. 	// If odd count is 2, then semi-eulerian. 
  98. 	// If odd count is 0, then eulerian 
  99. 	// Note that odd count can never be 1 for undirected graph 
  100. 	return (odd)? 1 : 2; 
  101. } 
  102.  
  103. // Function to run test cases 
  104. void test(Graph &g) 
  105. { 
  106. 	int res = g.isEulerian(); 
  107. 	if (res == 0) 
  108. 		cout << "graph is not Eulerian\n"; 
  109. 	else if (res == 1) 
  110. 		cout << "graph has a Euler path\n"; 
  111. 	else
  112. 		cout << "graph has a Euler cycle\n"; 
  113. } 
  114.  
  115. // Driver program to test above function 
  116. int main() 
  117. { 
  118. 	// Let us create and test graphs shown in above figures 
  119. 	Graph g1(5); 
  120. 	g1.addEdge(1, 0); 
  121. 	g1.addEdge(0, 2); 
  122. 	g1.addEdge(2, 1); 
  123. 	g1.addEdge(0, 3); 
  124. 	g1.addEdge(3, 4); 
  125. 	test(g1); 
  126.  
  127. 	Graph g2(5); 
  128. 	g2.addEdge(1, 0); 
  129. 	g2.addEdge(0, 2); 
  130. 	g2.addEdge(2, 1); 
  131. 	g2.addEdge(0, 3); 
  132. 	g2.addEdge(3, 4); 
  133. 	g2.addEdge(4, 0); 
  134. 	test(g2); 
  135.  
  136. 	Graph g3(5); 
  137. 	g3.addEdge(1, 0); 
  138. 	g3.addEdge(0, 2); 
  139. 	g3.addEdge(2, 1); 
  140. 	g3.addEdge(0, 3); 
  141. 	g3.addEdge(3, 4); 
  142. 	g3.addEdge(1, 3); 
  143. 	test(g3); 
  144.  
  145. 	// Let us create a graph with 3 vertices 
  146. 	// connected in the form of cycle 
  147. 	Graph g4(3); 
  148. 	g4.addEdge(0, 1); 
  149. 	g4.addEdge(1, 2); 
  150. 	g4.addEdge(2, 0); 
  151. 	test(g4); 
  152.  
  153. 	// Let us create a graph with all veritces 
  154. 	// with zero degree 
  155. 	Graph g5(3); 
  156. 	test(g5); 
  157.  
  158. 	return 0; 
  159. } 
  160.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
graph has a Euler path
graph has a Euler cycle
graph is not Eulerian
graph has a Euler cycle
graph has a Euler cycle
https://ideone.com/whW86r
language:
C++14 (gcc 8.3)
created:
5 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!