counting_paths_dag.cpp

// Directed Acyclic GRAPH
// counting number of paths
// paths (x) denote the number of paths from node a to node x . As a base case paths(a)=1
// vertices start from 1 onwards
#include <bits/stdc++.h>
using namespace std;

class Graph{
    int vertices;
    vector<int>*adj;
    bool cycle=false;
    int *visited;
    stack<int>stk;
public:
    Graph(int v);
    ~Graph(){
        delete [] adj;
        delete [] visited;
        cout<<"\n";
    }
    void addedge(int a,int b);
    void visit_false();
    void dfs_util(int s);
    void topological_sort_path();
};
Graph::Graph(int v){
    vertices=v;
    adj=new vector<int>[v];
    visited=new int[v];
}
void Graph::addedge(int a,int b){
    adj[a].push_back(b);
}
void Graph::visit_false(){
    for(int i=0;i<vertices;i++){
        visited[i]=0;
    }
}
void Graph::dfs_util(int s){
    if(cycle){
        return;
    }
    if(visited[s]==1){
        cycle=true;
        return;
    }
    if(visited[s]==2){
        return;
    }
    // cout<<s+1<<" ";
    visited[s]=1;
    for(auto u: adj[s]){
        if(cycle){
            return;
        }
        dfs_util(u);
    }
    stk.push(s);
    visited[s]=2;
}
void Graph::topological_sort_path(){
    visit_false();
    for(int i=0;i<vertices;i++){
        if(visited[i]==2){
            continue;
        }
        if(cycle){
            break;
        }
        dfs_util(i);
    }
    if(cycle){
        cout<<"there is a cycle,topological sort not possible\n";
        return;
    }
    int path[vertices];
    memset(path,0,sizeof(path));
    path[stk.top()]=1;
    while(!stk.empty()){
        for(int i=0;i<adj[stk.top()].size();i++){
            path[adj[stk.top()][i]]+=path[stk.top()];
        }
        stk.pop();
    }
    for(int i=0;i<vertices;i++){
        cout<<i+1<<" :"<<path[i]<<" paths\n";
    }
}

int main() {
    int vertices,edges;
    cout<<"Enter no of vertices & edges\n";
    cin>>vertices>>edges;
    Graph g(vertices);
    cout<<"Enter pair of adjacent vertices\n";
    for(int i=0;i<edges;i++){
        int a,b;
        cin>>a>>b;
        g.addedge(a-1,b-1);
    }
    cout<<" no of paths from a to b\n";
        g.topological_sort_path();

	return 0;
}

// if f(u) be the number of ways one can travel from node u to destination vertex. Hence, f(source) is required answer. As f(destination) = 1
// in this case we have to traverse reverse topological sort of graph

// input
/*
6 7
1 2
1 4
4 5 
2 3
2 6
5 2
3 6
*/