Euler order

[Pen72]

Good morning, I'm trying to write a program to print the Euler Tour order on a tree.
But the code isn't successful, is there any problem regarding the way I input data, many many thanks.


We assume the root of the tree is node 0.

Input Format

The first line is n, which is the size of tree .

The following n lines are information of children of nodes

The i-th line represents the child nodes of node i, 0<=i<=n.
The first integer,c , in i-th line represents number of children of node i , and the remaining c integers represents the children of node i.

Constraints
0<=n<=10000


Sample Input

6
1 1
2 2 3
0
2 4 5
0
0
Sample Output

Euler tour: 0 1 2 2 3 4 4 5 5 3 1 0

#include <bits/stdc++.h>
using namespace std;
 
#define MAX 10000

vector<int> adj[MAX];
 
int vis[MAX];
 
int Euler[2 * MAX];
 
void add_edge(int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void eulerTree(int u, int &index)
{
    vis[u] = 1;
    Euler[index++] = u;
    for (auto it : adj[u]) {
        if (!vis[it]) {
            eulerTree(it, index);
            Euler[index++] = u;
        }
    }
}
 
void printEulerTour(int root, int N)
{
    int index = 0; 
    eulerTree(root, index);
    for (int i = 0; i < (2*N-1); i++)
        cout << Euler[i] << " ";
}
 
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
       int i,node=0;
       cin>>i;
        while(i--)
        {  int u; cin>>u;
           add_edge(node, u);}
        node++;
    
    }
 
    cout<<"Euler tour:"<<"\n";
    printEulerTour(0, N);
 
    return 0;
}

[lastchance]

Can you explain the sample output?

If you write the tour in terms of nodes you get (e.g.)
0 1 2 1 3 4 3 5 3 1 0

If you write the tour in terms of edges (in the order they are defined) then you get
1 2 2 3 4 4 5 5 3 1

So, it looks like the intended output writes the edge numbers with a 0 at the ends. Is that the convention?

[Peter87]

It looks like you're not passing the correct value as first argument to add_edge.

Be careful with modifying variables that you might want to use later. The second argument to printEulerTour is incorrect thanks to this.

[lastchance]

#include <iostream>
#include <vector>
#include <map>
using namespace std;

//==========================================================

void printTour( const vector< vector<int> > &graph, map< pair<int,int>, int > &edgeNumber, int a )
{
   for ( int b : graph[a] )
   {
      int edge = edgeNumber[{a,b}];              
      cout << edge << ' ';                       // If printing edges rather than nodes
      printTour( graph, edgeNumber, b );
      cout << edge << ' ';                       // If printing edges rather than nodes
   }
}

//==========================================================

int main()
{
   istringstream in();
   int n;
   cin >> n;
   vector< vector<int> > graph( n );
   
   map< pair<int,int>, int > edgeNumber;
   int e = 0;
   
   for ( int i = 0; i < n; i++ )
   {
      int c, j;
      cin >> c;
      while( c-- )
      {
         cin >> j;
         graph[i].push_back( j );      // One-way relationship (parent -> child)
         edgeNumber[{i,j}] = ++e;
      }
   }

   cout << 0 << ' ';                   // This shouldn't really be necessary
   printTour( graph, edgeNumber, 0 );
   cout << 0 << ' ';
}

0 1 2 2 3 4 4 5 5 3 1 0 

[Pen72]

Hello. Euler Tour order is walking along the edges of the tree and hitting each node 2 times, the moment when a node is visited at the first time and the moment when all children of the node are visited. So yes I think it's in terms of edges.
I tried your code it passed the two sample test cases:
Sample Input 0

3
1 1
1 2
0

Sample Input 1

6
1 1
2 2 3
0
2 4 5
0
0

and shows wrong answers in the rest eight cases, but I can't see the input of them.

[lastchance]

Actually, there seem to be different ways of labelling it: GeeksForGeeks uses nodes, whilst Wikipedia uses edges (and doesn't require the 0 at each end, because that is a node not an edge, and it's supposed to be cyclic if it is a "tour").

If you use edges then you have to decide what their number is. I've just taken it as the order in which they are (implicitly) defined, and counting from 1.


Note that there is more than one possible Euler tour - you are entitled to take the subtrees defined by child nodes in any order you like. Also, depending on the number of children, individual nodes can be hit considerably more than 2 times. It is each EDGE which is only traversed twice (so each edge number should occur precisely twice in the edge output).


Anyway, DRAW THE TREE!

   (1)       (3)       (5)
0 ------ 1 ------- 3 ------- 5
         |         |
      (2)|      (4)|
         |         |
         2         4

Nodes as simple numbers; edges (in the order they are defined) in brackets.

[lastchance]

This one simply orders the edge numbers in a different way.

It will give the same answer for the given sample, but different answers for more complex trees.

Do you have a link to the original question (not your rephrasing of it). There needs to be an explanation of how you assign the edge numbers.

#include <iostream>
#include <vector>
using namespace std;

//==========================================================

void printTour( const vector< vector<int> > &graph, int &edge, int a )
{
   for ( int b : graph[a] )
   {
      int store = edge;
      cout << edge << ' ';
      edge++;                          // Ready for new edge
      printTour( graph, edge, b );
      cout << store << ' ';
   }
}

//==========================================================

int main()
{
   istringstream in();
   int n;
   cin >> n;
   vector< vector<int> > graph( n );
   
   for ( int i = 0; i < n; i++ )
   {
      int c, j;
      cin >> c;
      while( c-- )
      {
         cin >> j;
         graph[i].push_back( j );      // One-way relationship (parent -> child)
      }
   }

   int edge = 1;                       // "First" edge number
   cout << 0 << ' ';                   // This shouldn't really be necessary
   printTour( graph, edge, 0 );
   cout << 0 << ' ';                   // Nor this
}

[Pen72]

Hi thanks for the reply. Yes I feel that the 0 makes no sense too if we're traversing edge. The link can't be accessed from outsides, while there's this pic https://postimg.cc/FfX7SBCh and also, stated to visit children of a node in input order.

[lastchance]

Pen72 wrote:

to visit children of a node in input order.

That's still not enough to define the edge numbering.

Could you tell me if the last code worked? If not, there is only one other realistic ordering that I could try. Unfortunately, the given simple example cannot distinguish between possible ways of ordering edge numbers.

[Pen72]

No, it shows the same as the previous attempt. Passed two and got eight wrong ans.

[lastchance]

OK, one last try then. (EDIT: second thoughts ... this is rubbish. Try the post after.)

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

//==========================================================

void printTour( const vector< vector<int> > &graph, map< pair<int,int>, int > &edgeNumber, int a )
{
   for ( int b : graph[a] )
   {
      int edge = edgeNumber[{a,b}];              
      cout << edge << ' ';
      printTour( graph, edgeNumber, b );
      cout << edge << ' ';
   }
}

//==========================================================

int main()
{
   istringstream in();
   int n;
   cin >> n;
   vector< vector<int> > graph( n );        // Collection of children for each node
   set< pair<int,int> > edges;              // collection of edges (parent,child)

   for ( int i = 0; i < n; i++ )
   {
      int c, j;
      cin >> c;
      while( c-- )
      {
         cin >> j;
         graph[i].push_back( j );           // One-way relationship (parent -> child)
         edges.insert( { i, j } );
      }
   }

   map< pair<int,int>, int > edgeNumber;    // Edges assigned a number in lexicographical order
   int e = 0;
   for ( auto p : edges ) edgeNumber[p] = ++e;

   cout << 0 << ' ';                        // This shouldn't really be necessary
   printTour( graph, edgeNumber, 0 );
   cout << 0 << ' ';                        // Nor this
}

[lastchance]

Or even, second last try! (Edge number simply taken as that of the child node). Can at least mimic the Wikipedia article now.

#include <iostream>
#include <vector>
using namespace std;

//==========================================================

void printTour( const vector< vector<int> > &graph, int a )
{
   for ( int b : graph[a] )
   {
      cout << b << ' ';
      printTour( graph, b );
      cout << b << ' ';
   }
}

//==========================================================

int main()
{
   istringstream in();
   int n;
   cin >> n;
   vector< vector<int> > graph( n );        // Collection of children for each node

   for ( int i = 0; i < n; i++ )
   {
      int c, j;
      cin >> c;
      while( c-- )
      {
         cin >> j;
         graph[i].push_back( j );           // One-way relationship (parent -> child)
      }
   }

   cout << 0 << ' ';                        // This shouldn't really be necessary
   printTour( graph, 0 );
   cout << 0 << ' ';                        // Nor this
}

If I guess that the Wikipedia input corresponds to

7
3 1 3 5
2 2 4
1 6
0
0
0
0

then this gives (reasonably correctly) for that

0 1 2 6 6 2 4 4 1 3 3 5 5 0 

[Pen72]

Hello, thanks a lot for the great help!Passed all cases now.