  #include <iostream>

#include <vector>

#include <>

using namespace std;

// structure to store graph edges

struct Edge {

int src, dest;

};

// class to represent a graph object

class Graph

{

public:

// a vector of vectors to represent an adjacency list

// construct another vector for storing in-degree of the vertices

vector<int> indegree;

// Graph Constructor

Graph(vector<Edge> const &edges, int N)

{

// resize the adjacency list to N elements of type vector<int>

// resize the in-degree vector for N vertices

indegree.resize(N);

// add edges to the directed graph

for (auto &edge: edges) {

// increment in-degree of destination vertex by 1

indegree[edge.dest]++;

}

}

};

// Utility function to print a std::list

void printPath(list<int> list)        // no ref, no const

{

while (!list.empty()) {

cout << list.front() << ‘ ‘;

list.pop_front();

}

cout << endl;

}

// Recursive function to all of a given

void findAllTopologicalOrders(Graph &graph, auto &path,

auto &discovered, int N)

{

// do for every vertex

for (int v = 0; v < N; v++)

{

// proceed only if in-degree of current node is 0 and

// current node is not processed yet

if (graph.indegree[v] == 0 && !discovered[v])

{

// for every adjacent vertex u of v, reduce in-degree of u by 1

for (int u: graph.adjList[v]) {

graph.indegree[u];

}

// include current node in the path and mark it as discovered

path.push_back(v);

discovered[v] = true;

// recur

findAllTopologicalOrders(graph, path, discovered, N);

// backtrack: reset in-degree information for the current node

for (int u: graph.adjList[v]) {

graph.indegree[u]++;

}

// backtrack: remove current node from the path and

// mark it as undiscovered

path.pop_back();

discovered[v] = false;

}

}

// print the topological order if all vertices are included in the path

if (path.size() == N) {

printPath(path);

}

}

// Print all topological orderings of a given DAG

void printAllTopologicalOrders(Graph &graph)

{

// get number of nodes in the graph

int N = graph.adjList.size();

// create an auxiliary array to keep track of whether vertex is discovered

vector<bool> discovered(N);

// list to store the topological order

list<int> path;

// find all topological ordering and print them

findAllTopologicalOrders(graph, path, discovered, N);

}

int main()

{

// vector of graph edges as per above diagram

vector<Edge> edges =

{

{0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0},

{3, 4}, {5, 1}, {7, 0}, {7, 1}

};

// Number of nodes in the graph

int N = 8;

// create a graph from edges

Graph graph(edges, N);

// print all topological ordering of the graph

printAllTopologicalOrders(graph);

return 0;

}

SHARE