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 :

Detect if the node n is reachable from node 1.
Its its not then the required ans is 0
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
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

This is an interviewstreet challenge question - i.e. people are expected to use their ability to solve these to promote themselves to employers. — Ronald
– Ronald, Commented May 13, 2012 at 7:05

Community · Accepted Answer · 2020-06-20 09:12:55Z

4

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).

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered May 13, 2012 at 7:35

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

amitkarmakar Over a year ago

We can have a path A->B->A->C and other paths like A->B->A->B->A->B->A->C so there are infinite paths in that case

amit Over a year ago

@amit.codename13. True, the example is wrong, but the idea is not. let me re-make it. Have a look at it now. Also, note that the suggested algorithm would have caught the bad example I gave, and would have produced infinite paths for it.

btilly · Accepted Answer · 2012-05-13 07:48:25Z

2

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.

answered May 13, 2012 at 7:48

btilly

47.8k3 gold badges69 silver badges101 bronze badges

Comments

nhahtdh · Accepted Answer · 2012-09-23 08:30:03Z

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;
}

Collectives™ on Stack Overflow

Calculate Number of path between two nodes

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related