Pagini recente » Cod sursa (job #174364) | Cod sursa (job #1094737) | Cod sursa (job #664517) | Cod sursa (job #828204) | Cod sursa (job #3217484)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int MAX_SIZE = 100000;
vector<int> graph[MAX_SIZE + 1];
vector<int> answer;
map<pair<int, int>, bool> visitedEdge;
bool isVisited[MAX_SIZE + 1];
void bfs(vector<int> currentNodes) {
if (currentNodes.empty() == 1) {
return;
}
vector<int> nextNodes;
for (vector<int>::iterator it = currentNodes.begin(); it != currentNodes.end(); ++it) {
for (vector<int>::iterator it2 = graph[*it].begin(); it2 != graph[*it].end(); ++it2) {
if (isVisited[*it2] == 0) {
isVisited[*it2] = 1;
nextNodes.push_back(*it2);
}
}
}
bfs(nextNodes);
}
void euler(int currentNode) {
while (graph[currentNode].empty() == 0) {
if (visitedEdge[{currentNode, graph[currentNode].front()}] == 0) {
visitedEdge[{currentNode, graph[currentNode].front()}] = 1;
visitedEdge[{graph[currentNode].front(), currentNode}] = 1;
euler(graph[currentNode].front());
}
}
answer.push_back(currentNode);
}
bool isEuler(int noNodes) {
for (int i = 1; i <= noNodes; ++i) {
if (graph[i].size() % 2 == 1) {
return 0;
}
}
vector<int> currentNodes;
currentNodes.push_back(1);
isVisited[1] = 1;
bfs(currentNodes);
for (int i = 1; i <= noNodes; ++i) {
if (isVisited[i] == 0) {
return 0;
}
}
return 1;
}
int main() {
int noNodes, noEdges;
fin >> noNodes >> noEdges;
for (int i = 1; i <= noEdges; ++i) {
int startNode, endNode;
fin >> startNode >> endNode;
graph[startNode].push_back(endNode);
graph[endNode].push_back(startNode);
}
if (isEuler(noNodes) == 0) {
fout << -1;
} else {
euler(1);
for (int i = 0; i < answer.size(); ++i) {
fout << answer[i] << ' ';
}
}
return 0;
}