Pagini recente » Cod sursa (job #2435220) | Cod sursa (job #2617449) | Cod sursa (job #2564754) | Cod sursa (job #683018) | Cod sursa (job #2820761)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cassert>
#define Max 100005
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int N, M;
vector < pair<int,int> > edges[Max];
class Graph{
private:
int NumberOfNodes, NumberOfEdges;
vector<int> adjacencyList[Max];
public:
Graph(int N, int M); // constructor
void Euler(int k, int &ct, vector <int>&solutions, int visited[5*Max]);
void Eulerian_Cycle();
};
// constructor
Graph :: Graph(int N, int M)
{
NumberOfNodes = N;
NumberOfEdges = M;
}
void Graph :: Euler(int k, int &ct, vector <int>&solutions, int visited[5*Max])
{
while( !edges[k].empty() )
{
//x = indicele muchiei
//M[x].first = k
//M[x].second = cealalta extremitate
int edge = edges[k].back().first;
int next = edges[k].back().second;
if( visited[edge] == 0 )
{
visited[edge] = 1;
Euler(next, ct, solutions, visited);
}
}
ct++;
solutions.push_back(k);
}
void Graph :: Eulerian_Cycle ()
{
int x, y, i = 1;
while ( fin >> x >> y )
{
edges[x].push_back({i, y});
edges[y].push_back({i, x});
i++;
}
for ( int i = 1; i <= NumberOfNodes; i++ )
if ( edges[i].size() % 2 )
{
fout << "-1";
return;
}
int visited[5*Max] = {0};
int ct = 0;
vector<int> solutions;
Euler(1, ct, solutions, visited);
solutions.pop_back();
for ( auto i : solutions )
fout << i << " ";
}
int main()
{
fin >> N >> M;
Graph G(N, M);
G.Eulerian_Cycle();
return 0;
}