DFS All paths to destination

dfs-all-paths-dest.cpp

#include <iostream>
#include <vector>
#include <math.h>
#include <unordered_map>
#include <string>
#include <fstream>
#include <stack>
using namespace std;

unordered_map<int, vector<int>> graph;
bool visited[6]{};

vector<vector<int>> paths;
vector<int> currentPath;

void dfsAllPaths(int currentVertex, int targetVertex) {
  if (currentVertex == targetVertex) {
    currentPath.push_back(targetVertex);

    paths.push_back(currentPath);

    currentPath.pop_back();

    return;
  }

  if (!visited[currentVertex]) {
    visited[currentVertex] = true;

    currentPath.push_back(currentVertex);

    for (int neigh : graph[currentVertex]) {
      dfsAllPaths(neigh, targetVertex);
    }

    currentPath.pop_back();

    visited[currentVertex] = false;
  }
}

int main() {
  graph[0] = {1, 2, 3};
  graph[1] = { 0, 4, 5 };
  graph[2] = { 0, 4 };
  graph[3] = { 0, 4 };
  graph[4] = { 2, 3, 1, 5 };
  graph[5] = { 1, 4 };

  
  dfsAllPaths(0, 1);

  for (auto& path : paths) {
    for (int i = 0; i < path.size(); i++) {
      cout << path[i] << " ";
    }
    cout << endl;
  }

}