#include <iostream>
#include <vector>
using namespace std;
// data structure to store graph edges
struct Edge {
int src, dest;
};
// class to represent a graph object
class Graph
{
public:
// construct a vector of vectors to represent adjacency list in C++
vector<vector<int>> adjList;
// Graph Constructor
Graph(const vector<Edge> &edges, int N)
{
// resize the vector to N elements of type vector<int>
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// Utility function to print a vector
void printPath(const vector<int> &path)
{
for (int i: path)
cout << i << ' ';
cout << endl;
}
// Function to perform DFS traversal in a directed graph to find the
// complete path between source and destination vertices
void printAllPaths(const Graph &graph, int src, int dest,
vector<bool> &discovered, vector<int> &path)
{
// mark current node as discovered
discovered[src] = true;
// include current node in the path
path.push_back(src);
// print the complete path if destination vertex is found
if (src == dest) {
printPath(path);
}
// do for every edge (src -> i)
for (int i: graph.adjList[src])
{
// proceed if u is not discovered
if (!discovered[i]) {
printAllPaths(graph, i, dest, discovered, path);
}
}
// backtrack: remove current node from the path & mark it as not discovered
path.pop_back();
discovered[src] = false;
}
int main()
{
// vector of graph edges as per above diagram
vector<Edge> edges = {
{0, 3}, {1, 0}, {1, 2}, {1, 4}, {2, 7}, {3, 4},
{3, 5}, {4, 3}, {4, 6}, {5, 6}, {6, 7}
};
// Number of nodes in the graph (labelled from 0 to N-1)
int N = 8;
// create a graph from given edges
Graph graph(edges, N);
// stores vertex is discovered or not
vector<bool> discovered(N);
// source and destination vertex
int src = 0, dest = 7;
// vector to store the complete path between source and destination
vector<int> path;
// perform DFS traversal from the source vertex to check the connectivity
// and print all paths from the source vertex to the destination vertex
printAllPaths(graph, src, dest, discovered, path);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gZGF0YSBzdHJ1Y3R1cmUgdG8gc3RvcmUgZ3JhcGggZWRnZXMKc3RydWN0IEVkZ2UgewogICAgaW50IHNyYywgZGVzdDsKfTsKCi8vIGNsYXNzIHRvIHJlcHJlc2VudCBhIGdyYXBoIG9iamVjdApjbGFzcyBHcmFwaAp7CnB1YmxpYzoKICAgIC8vIGNvbnN0cnVjdCBhIHZlY3RvciBvZiB2ZWN0b3JzIHRvIHJlcHJlc2VudCBhZGphY2VuY3kgbGlzdCBpbiBDKysKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gYWRqTGlzdDsKCiAgICAvLyBHcmFwaCBDb25zdHJ1Y3RvcgogICAgR3JhcGgoY29uc3QgdmVjdG9yPEVkZ2U+ICZlZGdlcywgaW50IE4pCiAgICB7CiAgICAgICAgLy8gcmVzaXplIHRoZSB2ZWN0b3IgdG8gTiBlbGVtZW50cyBvZiB0eXBlIHZlY3RvcjxpbnQ+CiAgICAgICAgYWRqTGlzdC5yZXNpemUoTik7CgogICAgICAgIC8vIGFkZCBlZGdlcyB0byB0aGUgZGlyZWN0ZWQgZ3JhcGgKICAgICAgICBmb3IgKGF1dG8gJmVkZ2U6IGVkZ2VzKSB7CiAgICAgICAgICAgIGFkakxpc3RbZWRnZS5zcmNdLnB1c2hfYmFjayhlZGdlLmRlc3QpOwogICAgICAgIH0KICAgIH0KfTsKCi8vIFV0aWxpdHkgZnVuY3Rpb24gdG8gcHJpbnQgYSB2ZWN0b3IKdm9pZCBwcmludFBhdGgoY29uc3QgdmVjdG9yPGludD4gJnBhdGgpCnsKICAgIGZvciAoaW50IGk6IHBhdGgpCiAgICAgICAgY291dCA8PCBpIDw8ICcgJzsKICAgIGNvdXQgPDwgZW5kbDsKfQoKLy8gRnVuY3Rpb24gdG8gcGVyZm9ybSBERlMgdHJhdmVyc2FsIGluIGEgZGlyZWN0ZWQgZ3JhcGggdG8gZmluZCB0aGUKLy8gY29tcGxldGUgcGF0aCBiZXR3ZWVuIHNvdXJjZSBhbmQgZGVzdGluYXRpb24gdmVydGljZXMKdm9pZCBwcmludEFsbFBhdGhzKGNvbnN0IEdyYXBoICZncmFwaCwgaW50IHNyYywgaW50IGRlc3QsCiAgICAgICAgdmVjdG9yPGJvb2w+ICZkaXNjb3ZlcmVkLCB2ZWN0b3I8aW50PiAmcGF0aCkKewogICAgLy8gbWFyayBjdXJyZW50IG5vZGUgYXMgZGlzY292ZXJlZAogICAgZGlzY292ZXJlZFtzcmNdID0gdHJ1ZTsKCiAgICAvLyBpbmNsdWRlIGN1cnJlbnQgbm9kZSBpbiB0aGUgcGF0aAogICAgcGF0aC5wdXNoX2JhY2soc3JjKTsKCiAgICAvLyBwcmludCB0aGUgY29tcGxldGUgcGF0aCBpZiBkZXN0aW5hdGlvbiB2ZXJ0ZXggaXMgZm91bmQKICAgIGlmIChzcmMgPT0gZGVzdCkgewogICAgICAgIHByaW50UGF0aChwYXRoKTsKICAgIH0KCiAgICAvLyBkbyBmb3IgZXZlcnkgZWRnZSAoc3JjIC0+IGkpCiAgICBmb3IgKGludCBpOiBncmFwaC5hZGpMaXN0W3NyY10pCiAgICB7CiAgICAgICAgLy8gcHJvY2VlZCBpZiB1IGlzIG5vdCBkaXNjb3ZlcmVkCiAgICAgICAgaWYgKCFkaXNjb3ZlcmVkW2ldKSB7CiAgICAgICAgICAgIHByaW50QWxsUGF0aHMoZ3JhcGgsIGksIGRlc3QsIGRpc2NvdmVyZWQsIHBhdGgpOwogICAgICAgIH0KICAgIH0KCiAgICAvLyBiYWNrdHJhY2s6IHJlbW92ZSBjdXJyZW50IG5vZGUgZnJvbSB0aGUgcGF0aCAmIG1hcmsgaXQgYXMgbm90IGRpc2NvdmVyZWQKICAgIHBhdGgucG9wX2JhY2soKTsKICAgIGRpc2NvdmVyZWRbc3JjXSA9IGZhbHNlOwp9CgppbnQgbWFpbigpCnsKICAgIC8vIHZlY3RvciBvZiBncmFwaCBlZGdlcyBhcyBwZXIgYWJvdmUgZGlhZ3JhbQogICAgdmVjdG9yPEVkZ2U+IGVkZ2VzID0gewogICAgICAgIHswLCAzfSwgezEsIDB9LCB7MSwgMn0sIHsxLCA0fSwgezIsIDd9LCB7MywgNH0sCiAgICAgICAgezMsIDV9LCB7NCwgM30sIHs0LCA2fSwgezUsIDZ9LCB7NiwgN30KICAgIH07CgogICAgLy8gTnVtYmVyIG9mIG5vZGVzIGluIHRoZSBncmFwaCAobGFiZWxsZWQgZnJvbSAwIHRvIE4tMSkKICAgIGludCBOID0gODsKCiAgICAvLyBjcmVhdGUgYSBncmFwaCBmcm9tIGdpdmVuIGVkZ2VzCiAgICBHcmFwaCBncmFwaChlZGdlcywgTik7CgogICAgLy8gc3RvcmVzIHZlcnRleCBpcyBkaXNjb3ZlcmVkIG9yIG5vdAogICAgdmVjdG9yPGJvb2w+IGRpc2NvdmVyZWQoTik7CgogICAgLy8gc291cmNlIGFuZCBkZXN0aW5hdGlvbiB2ZXJ0ZXgKICAgIGludCBzcmMgPSAwLCBkZXN0ID0gNzsKCiAgICAvLyB2ZWN0b3IgdG8gc3RvcmUgdGhlIGNvbXBsZXRlIHBhdGggYmV0d2VlbiBzb3VyY2UgYW5kIGRlc3RpbmF0aW9uCiAgICB2ZWN0b3I8aW50PiBwYXRoOwoKICAgIC8vIHBlcmZvcm0gREZTIHRyYXZlcnNhbCBmcm9tIHRoZSBzb3VyY2UgdmVydGV4IHRvIGNoZWNrIHRoZSBjb25uZWN0aXZpdHkKICAgIC8vIGFuZCBwcmludCBhbGwgcGF0aHMgZnJvbSB0aGUgc291cmNlIHZlcnRleCB0byB0aGUgZGVzdGluYXRpb24gdmVydGV4CiAgICBwcmludEFsbFBhdGhzKGdyYXBoLCBzcmMsIGRlc3QsIGRpc2NvdmVyZWQsIHBhdGgpOwoKICAgIHJldHVybiAwOwp9