Calculate Number of path between two nodes

Question

Kingdom Connectivity

It has been a prosperous year for King Charles and he is rapidly expanding his kingdom.A beautiful new kingdom has been recently constructed and in this kingdom there are many cities connected by a number of one-way roads.Two cities may be directly connected by more than one roads, this is to ensure high connectivity.

In this new kingdom King Charles has made one of the cities at his financial capital and one as warfare capital and he wants high connectivity between these two capitals.The connectivity of a pair of cities say city A and city B is defined as the number of different paths from city A to city B. A path may use a road more than once if possible. Two paths are considered different if they do not use exactly the same sequence of roads.

There are N cities numbered 1 to N in the new kingdom and M one-way roads . City 1 is the monetary capital and city N is the warfare capital.

You being one of the best programmers in new kingdom need to answer the connectivity of financial capital and warfare capital ,i.e number of different paths from city 1 to city N.

Input Description:

First line contains two integers N and M.

Then follow M lines ,each having two integers say x and y, 1<=x,y<=N , indicating there is a road from city x to city y.

Output Description:

Print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9).If there are infinitely many different paths print "INFINITE PATHS"(quotes are for clarity).

Sample Input:

5 5 1 2 2 4 2 3 3 4 4 5

Sample Output:

2

Sample Input:

5 5 1 2 4 2 2 3 3 4 4 5

Sample Output:

INFINITE PATHS

Constraints:

2<=N<=10,000(10^4)

1<=M<=1,00,000(10^5)

Two cities may be connected by more than two roads and in that case those roads are to be considered different for counting distinct paths

The algorithm that i use to solve the problem is :

1. Detect if the node n is reachable from node 1.
2. Its its not then the required ans is 0
3. If its reachable then find if there is any cycle in the graph by doing dfs from node 0
4. If there is a cycle then print INFINITE PATHS

5. If there is no cycle calculate the required ans using the recurrence

   • F(n) = 1
   • F(0) = Sumofall F(x) such that x is adjacent to 0
   • F(x) = 0 if there is no x adjacent to x

I have implemented the solution as :

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<pair<int, int> > > g;

int seen[10001] = {0};

int colour[10001] = {0};
bool has_cycle(int u) {
    colour[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
            if(colour[g[u][i].first]==1) return true;
            if(!colour[g[u][i].first])
            if(has_cycle(g[u][i].first)) return true;
    }
    colour[u] = 2;
    return false;
}


bool reachable(int u, int v) {
     if(u==v) return true;
     seen[u] = true;
     for(int i = 0; i < g[u].size(); i++) {
             if(!seen[g[u][i].first]) {
                                      if(reachable(g[u][i].first, v)) return true;
             }
     }
     return false;
}

long long mm[10001] = {0};
long long solve(int u, int n) {
     if(u==n) return mm[u]=1;
     if(mm[u]!=-2) return mm[u];
     long long ans = 0;
     for(int i = 0; i < g[u].size(); i++) {
             ans += ((g[u][i].second%1000000000)*(solve(g[u][i].first, n)%1000000000)%1000000000);
             ans %= 1000000000;
     }
     return mm[u]=ans;
}

long edge[100001];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    g.resize(n);
    for(int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            x--; y--;
            edge[i] = x*100000+y;
    }

    sort(edge, edge+m);
    edge[m] = -1;
    int last = edge[0];
    int cnt = 1;
    for(int i = 1; i <= m; i++) {
            if(edge[i]!=last || i==m) {
                              int u, v;
                              u = last/100000;
                              v = last%100000;
                              if(i!=0) {       
                                       g[u].push_back(make_pair(v, cnt));
                              }
                              cnt = 1;
            } else {
                   cnt++;
            }
            last = edge[i];
    }


    for(int i = 0; i < n; i++) mm[i] = -2;
    if(reachable(0, n-1)) {
      if(has_cycle(0)) printf("INFINITE PATHS\n");
      else 
      printf("%lld\n", solve(0, n-1)%1000000000);
    } else printf("0\n");
}

I am not able to detect the problem with this algorithm

Answer 1

You can reference my code

#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include "string.h"
#define MODE 1000000000
using namespace std;

int main () {
    vector<int> adj[10001], inv_adj[10001];
    int indegree[10001];
    int visited[10001];
    int ranks[10001];
    long long total[10001];
    int N, M;
    cin >> N >> M;

    memset(indegree, 0, (N+1)*sizeof(int));
    adj[0].push_back(1); 
    inv_adj[1].push_back(0);
    indegree[1] = 1;
    for (int i=0;i<M;i++)
    {
        int s, t;
        cin >> s >> t;
        adj[s].push_back(t);
        inv_adj[t].push_back(s);
        indegree[t]++;
    }

    stack<int> st;
    st.push(0);
    memset(visited, 0, (N+1)*sizeof(int));
    visited[0] = 1;
    while (!st.empty()) {
        int v = st.top();
        st.pop();

        for (int i=0;i<adj[v].size();i++)
            if (!visited[adj[v][i]])
            {
                st.push(adj[v][i]);
                visited[adj[v][i]] = 1;
            }
    }

    if(!visited[N])
    {
        cout << 0 << endl;
        return 0;
    }

    for (int i=1;i<=N;i++)
    {
        if(!visited[i]){
            for (int j=0;j<adj[i].size();j++)
                indegree[adj[i][j]]--;
        }
    }

    int count = 0;
    stack<int> topo;

    for (int i=0;i<=N;i++)
    {
        int j;
        for (j=0;j<=N;j++)
            if (visited[j] && indegree[j] ==0)
                break;
        if (j > N)
        {
            cout << "INFINITE PATHS" << endl;
            return 0;
        }
        else
        {
            topo.push(j);
            ranks[count++] = j;
            if (j == N)
                break;

            indegree[j] = -1;
            for (int k=0;k<adj[j].size();k++)
                indegree[adj[j][k]]--;
        }
    }

    memset(total, 0, (N+1)*sizeof(long long));
    total[N] = 1;
    for (int i=count - 1;i>=0;i--)
    {
        int r = ranks[i];
        for (int j=0;j<inv_adj[r].size();j++)
            if(visited[inv_adj[r][j]])
            {
                total[inv_adj[r][j]] = (total[inv_adj[r][j]] + total[r]) % MODE;
            }
    }
    cout << total[0] << endl;
    return 0;
}

Answer 2

Number (3)+(4) are wrong:

If its reachable then find if there is any cycle in the graph by doing dfs from node 0.

If there is a cycle then print INFINITE PATHS

There could be a cycle in the graph, but the required #paths would still be a finite number, if the target is not reachable from the cycle.
Example: Looking for #paths from A to C

A-->D<-->B
|
----->C

In here: G=(V,E), V = {A,B,C,D} and E = {(D,B),(B,D),(A,C),(A,D)}

Though there is a cycle reachable from A (A->D->B->D), there is only one path from A to C.

To find if there are cycles in a path leading from source to target one can create a new graph G'=(V',E'), where V'= { v | there is a path in the original graph from v to target }, and E' = V' x V' [intersection] E (E reduced only to the vertices of V'), and run DFS/BFS on G'.

Also note, that if there are no cycles in G' - it is a DAG by definition, so working on G' from now on, will probably simplify also finding the #paths. (You will also have to trim vertices that are not reachable from source to make sure it is indeed a DAG).

Answer 3

Obvious mistake. Suppose that there is a cycle, but there is no path from the cycle to the second city. Then you will say that there are an infinite number of paths, but the number of paths may actually be finite.