// https://www.geeksforgeeks.org/count-possible-paths-two-vertices/
#include<iostream>
#include<list>
#include<vector>
using namespace std;
class graph {
int v;
list<int> *adj;
public:
graph(int v) {
this->v= v;
adj= new list<int> [v];
}
void addEdge (int u, int w) {
adj[u].push_back(w);
}
int CP (int s, int d);
void CPUtil (int, int, bool [], int&, vector <int> &);
};
int graph::CP (int s, int d) {
bool visited[v]={0};
int pc=0;
vector <int> v;
CPUtil (s,d,visited, pc,v);
return pc;
}
void graph::CPUtil(int s, int d, bool visited[], int &pc, vector <int> &v) {
visited[s]=1;
v.push_back(s);
if (s==d) {
pc++;
for (auto i=v.begin(); i!= v.end(); ++i)
cout<< *i << " ";
cout<< "\n";
}
else {
list<int>::iterator i;
for (i=adj[s].begin(); i!=adj[s].end();++i)
if (!visited[*i])
CPUtil(*i,d,visited, pc, v);
}
visited[s]=0;
v.erase(v.begin()+v.size()-1);
}
int main() {
graph g(5);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(0,3);
g.addEdge(1,4);
g.addEdge(1,3);
g.addEdge(2,4);
g.addEdge(3,2);
cout<< g.CP(0,4);
}
// https://www.geeksforgeeks.org/count-possible-paths-two-vertices/
#include <iostream>
#include <list>
using namespace std;
class graph {
int v;
list <int> *adj;
public:
graph (int v) {
this->v = v;
adj= new list<int> [v];
}
void addEdge (int u, int w) {
adj[u].push_back(w);
}
int countPaths (int s, int d);
void countPathUtil (int, int, bool [], int&);
};
int graph::countPaths(int s, int d) {
bool visited[v]= {0};
int pc = 0;
countPathUtil(s,d, visited, pc);
return pc;
}
void graph::countPathUtil(int s, int d, bool visited[], int &pc){
visited[s]=1;
if (s==d)
pc++;
else {
list<int>::iterator j;
for (j= adj[s].begin(); j!= adj[s].end(); ++j)
if (!visited[*j])
countPathUtil(*j,d,visited, pc);
}
visited[s]=0;
}
int main()
{
graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);
int s = 2, d = 3;
cout << g.countPaths(s, d);
return 0;
}