dsa/graphs/trees | desc: Euler walk

euler walk.cpp

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

int n;
vector<vector<int>> graph;
vector<int> euler_walk, in, out;

void dfs(int u, int &i, vector<bool> &vis){
  vis[u] = true;
  euler_walk[i++] = u;
  for (auto v : graph[u])
    if (!vis[v]) {
      dfs(v, i, vis);
      euler_walk[i++] = u;
    }
}

void dfs_in_out(int u, int &i, vector<bool> &vis){
  vis[u] = true;
  in[u] = ++i;
  for (auto v : graph[u])
    if (!vis[v]) dfs_in_out(v, i, vis);
  out[u] = i;
}

int main(){
  /*
              (0)
              /
          1 / 6
            /
          (1)
        /   \
      2 / 3 4 \ 5
      /       \
    (2)       (3)
  */

  /* **Directed graph** */
  n = 4;
  vector<bool> vis(n, false);
  graph.resize(n);
  euler_walk.resize(2 * n - 1);
  graph = {
    {1}, // 0
    {2, 3}, // 1
    {}, // 2
    {} // 3
  };

  /* Simple Euler walk */
  int i = 0;
  dfs(0, i, vis);
  for (auto j : euler_walk) cout << j << ""; // [0 1 2 1 3 1 0]
  cout << endl;

  /* In and Out concept
    > In: number when we first enter an vertex
    > Out: last number jo uss subgraph mai out hoga
              (0)
              /
          1 /
            /
          (1)
        /   \
      2 /   3 \
      /       \
    (2)       (3)

    Vertex: 0   1   2   3
    ---------------------
    In:     0   1   2   3
    Out:    3   3   2   3
  */

  in.resize(n);
  out.resize(n);
  i = -1;

  fill(vis.begin(), vis.end(), false);

  dfs_in_out(0, i, vis);

  cout << "In: ";
  for (auto j : in) cout << j << " ";
  cout << "\nOut: ";
  for(auto j : out) cout << j << " ";

  return 0;
}