Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Print Euler Path
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
// A C++ program print Eulerian Trail in a given Eulerian or Semi-Eulerian Graph #include <iostream> #include <string.h> #include <algorithm> #include <list> using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency lists public: // Constructor and destructor Graph(int V) { this->V = V; adj = new list<int>[V]; } ~Graph() { delete [] adj; } // functions to add and remove edge void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } void rmvEdge(int u, int v); // Methods to print Eulerian tour void printEulerTour(); void printEulerUtil(int s); // This function returns count of vertices reachable from v. It does DFS int DFSCount(int v, bool visited[]); // Utility function to check if edge u-v is a valid next edge in // Eulerian trail or circuit bool isValidNextEdge(int u, int v); }; /* The main function that print Eulerian Trail. It first finds an odd degree vertex (if there is any) and then calls printEulerUtil() to print the path */ void Graph::printEulerTour() { // Find a vertex with odd degree int u = 0; for (int i = 0; i < V; i++) if (adj[i].size() & 1) { u = i; break; } // Print tour starting from oddv printEulerUtil(u); cout << endl; } // Print Euler tour starting from vertex u void Graph::printEulerUtil(int u) { // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // If edge u-v is not removed and it's a a valid next edge if (v != -1 && isValidNextEdge(u, v)) { cout << u << "-" << v << " "; rmvEdge(u, v); printEulerUtil(v); } } } // The function to check if edge u-v can be considered as next edge in // Euler Tout bool Graph::isValidNextEdge(int u, int v) { // The edge u-v is valid in one of the following two cases: // 1) If v is the only adjacent vertex of u int count = 0; // To store count of adjacent vertices list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) if (*i != -1) count++; if (count == 1) return true; // 2) If there are multiple adjacents, then u-v is not a bridge // Do following steps to check if u-v is a bridge // 2.a) count of vertices reachable from u bool visited[V]; memset(visited, false, V); int count1 = DFSCount(u, visited); // 2.b) Remove edge (u, v) and after removing the edge, count // vertices reachable from u rmvEdge(u, v); memset(visited, false, V); int count2 = DFSCount(u, visited); // 2.c) Add the edge back to the graph addEdge(u, v); // 2.d) If count1 is greater, then edge (u, v) is a bridge return (count1 > count2)? false: true; } // This function removes edge u-v from graph. It removes the edge by // replacing adjcent vertex value with -1. void Graph::rmvEdge(int u, int v) { // Find v in adjacency list of u and replace it with -1 list<int>::iterator iv = find(adj[u].begin(), adj[u].end(), v); *iv = -1; // Find u in adjacency list of v and replace it with -1 list<int>::iterator iu = find(adj[v].begin(), adj[v].end(), u); *iu = -1; } // A DFS based function to count reachable vertices from v int Graph::DFSCount(int v, bool visited[]) { // Mark the current node as visited visited[v] = true; int count = 1; // Recur for all vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (*i != -1 && !visited[*i]) count += DFSCount(*i, visited); return count; } // Driver program to test above function int main() { // Let us first create and test graphs shown in above figure Graph g1(4); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(2, 3); g1.printEulerTour(); Graph g2(3); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 0); g2.printEulerTour(); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(3, 2); g3.addEdge(3, 1); g3.addEdge(2, 4); g3.printEulerTour(); return 0; }
g++
Show compiler warnings
[
+
] Compiler args
[
+
]
Show input
Compilation time: 1.03 sec, absolute running time: 0.08 sec, cpu time: 0.02 sec, memory peak: 3 Mb, absolute service time: 1,14 sec
edit mode
|
history
|
discussion
2-0 0-1 1-2 2-3 0-1 1-2 2-0 0-1 1-2 2-0 0-3 3-4 4-2 2-3 3-1