1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
// Eulerian trail:
// Must visit every EDGE exactly once
// Can visit every node as many times as desired
// Is Eulerian cycle if start point equals end point
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int startIndex = 1; // I presume
const int source = startIndex;
//==========================================================
// Main backtracking routine
bool solve( int num, int a, int m, const vector<vector<int>> &graph, map<pair<int,int>,bool> &edgeVisited, vector<int> &route )
{
route[num] = a;
if ( num == m )
{
if ( a == source ) return true;
else return false;
}
for ( int b : graph[a] )
{
if ( !edgeVisited[{a,b}] )
{
edgeVisited[{a,b}] = edgeVisited[{b,a}] = true;
if ( solve( num + 1, b, m, graph, edgeVisited, route ) ) return true; // Key recursion
edgeVisited[{a,b}] = edgeVisited[{b,a}] = false;
}
}
return false;
}
//==========================================================
int main()
{
int T;
cin >> T;
while ( T-- )
{
int n, m;
cin >> n >> m;
map<pair<int,int>,bool> edgeVisited;
vector< vector<int> > graph( n + startIndex );
vector<int> route( 1 + m );
for ( int i = 0; i < m; i++ )
{
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
edgeVisited[{a,b}] = edgeVisited[{b,a}] = false;
}
if ( solve( 0, source, m, graph, edgeVisited, route ) )
{
cout << "Route: ";
for ( auto e : route ) cout << e << " ";
cout << '\n';
}
else
{
cout << "No Eulerian cycle\n";
}
}
}
|