Pagini recente » Cod sursa (job #352398) | Cod sursa (job #1385824) | Cod sursa (job #1390042) | Cod sursa (job #845103) | Cod sursa (job #2821631)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define Max 100005
#define Max2 500005
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 Eulerian_Cycle();
void Euler(int k, int &ct, vector <int>&solutions, int visited[Max2]);
};
// constructor
Graph :: Graph(int N, int M)
{
NumberOfNodes = N;
NumberOfEdges = M;
}
void Graph :: Euler(int k, int &ct, vector <int>&solutions, int visited[Max2])
{
while( !edges[k].empty() )
{
//x = indicele muchiei
//edges[x].first = k
//edges[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); // adaug k la ciclu
}
void Graph :: Eulerian_Cycle ()
{
int x, y;
for ( int i = 1; i <= NumberOfEdges; i++ )
{
fin >> x >> y;
edges[x].push_back( make_pair(i, y) );
edges[y].push_back( make_pair(i, x) );
}
// daca nu avem ciclu eulerian
for ( int i = 1; i <= NumberOfNodes; i++ )
if ( edges[i].size() % 2 )
{
fout << "-1";
return;
}
int visited[Max2] = {0}, ct = 0;
vector<int> solutions;
Euler(1, ct, solutions, visited);
solutions.pop_back();
// afisare
for ( auto i : solutions )
fout << solutions[i] << " ";
}
int main()
{
fin >> N >> M;
Graph G(N, M);
G.Eulerian_Cycle();
return 0;
}