#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
class Graph {
public:
Graph(int V) {
this->V = V;
adj = new vector<int>[V];
}
void AddEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
bool isConnected() {
vector<bool> visited(V, false);
int i;
for (i = 0; i < V; i++)
if (adj[i].size() != 0)
break;
if (i == V)
return true;
DFSUtil(i, visited);
for (i = 0; i < V; i++)
if (visited[i] == false && adj[i].size() > 0)
return false;
return true;
}
int isEulerian() {
if (isConnected() == false)
return 0;
int odd = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1)
odd++;
if (odd > 2)
return 0;
return (odd) ? 1 : 2;
}
void printEulerUtil(int s) {
stack<int> st;
st.push(s);
while (!st.empty()) {
int u = st.top();
st.pop();
for (int i = 0; i < adj[u].size(); i++); {
int v = adj[u][i]; \\\ тут выдает ошибку
if (isValidNextEdge(u, v)) {
cout << u << "-" << v << " ";
removeEdge(u, v);
st.push(v);
}
}
}
}
void printEulerTour() {
int u = 0;
for (int i = 0; i < V; i++)
if (adj[i].size() & 1) {
u = i;
break;
}
printEulerUtil(u);
cout << endl;
}
private:
int V;
vector<int>* adj;
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
for (auto i = adj[v].begin(); i != adj[v].end(); i++)
if (!visited[*i])
DFSUtil(*i, visited);
}
bool isValidNextEdge(int u, int v) {
int count = 0;
for (auto i = adj[u].begin(); i != adj[u].end(); i++)
if (*i != -1)
count++;
if (count == 1)
return true;
vector<bool> visited(V, false);
int count1 = DFSCount(u, visited);
removeEdge(u, v);
visited.assign(V, false);
int count2 = DFSCount(u, visited);
AddEdge(u, v);
return (count1 > count2) ? false : true;
}
int DFSCount(int v, vector<bool>& visited) {
visited[v] = true;
int count = 1;
for (auto i = adj[v].begin(); i != adj[v].end(); i++)
if (!visited[*i] && *i != -1)
count += DFSCount(*i, visited);
return count;
}
void removeEdge(int u, int v) {
for (auto i = adj[u].begin(); i != adj[u].end(); i++) {
if (*i == v) {
*i = -1;
break;
}
}
for (auto i = adj[v].begin(); i != adj[v].end(); i++) {
if (*i == u) {
*i = -1;
break;
}
}
}
};
int main() {
ifstream fin("graph.txt");
int V, E;
fin >> V >> E;
Graph gr(V);
int u, v;
for (int i = 0; i < E; i++) {
fin >> u >> v;
gr.AddEdge(u, v);
}
int res = gr.isEulerian();
if (res == 0)
cout << "Graph is not Eulerian\n";
else if (res == 1)
cout << "Graph has Eulerian path\n";
else
cout << "Graph has Eulerian cycle\n";
gr.printEulerTour();
fin.close();
return 0;