HackerRank Kingdom Connectivity problem solution

In this HackerRank Kingdom Connectivity problem solution, there are n cities numbered 1 to n in the new kingdom and m one-way roads. City 1 is the financial capital and city n is the warfare capital. Determine the number of different paths between cities 1 and n.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys
import collections

MOD = 1000000000


#
# Complete the 'countPaths' function below.
#
# The function accepts following parameters:
#  1. INTEGER n
#  2. 2D_INTEGER_ARRAY edges
#

def countPaths(n, edges):
  graph = collections.defaultdict(list)

  for i, j in edges:
    graph[i - 1].append(j - 1)

  start = 0
  end = n - 1

  memo = [0] * n
  cycle_nodes = set()
  path_nodes = set()

  path = []
  seen = [False] * n

  def update_path_nodes(inc):
    for cur in path:
      path_nodes.add(cur)
      memo[cur] += inc
      memo[cur] %= MOD

  def update_cycle_nodes(cycle_start):
    k = len(path) - 1
    while path[k] != cycle_start:
      cycle_nodes.add(path[k])
      k -= 1
    cycle_nodes.add(cycle_start)

  def dfs(node):
    path.append(node)
    seen[node] = True

    if node == n - 1:
      update_path_nodes(1)
    else:
      for next in graph[node]:
        if seen[next]:
          update_cycle_nodes(next)
        else:
          if memo[next] > 0:
            update_path_nodes(memo[next])
          if memo[next] == 0:
            dfs(next)

    if memo[node] == 0:
      memo[node] = -1

    seen[node] = False
    path.pop()

  dfs(start)
  if len(cycle_nodes.intersection(path_nodes)) > 1:
    print('INFINITE PATHS')
  else:
    print(memo[start])


if __name__ == '__main__':
  first_multiple_input = input().rstrip().split()

  nodes = int(first_multiple_input[0])

  m = int(first_multiple_input[1])

  edges = []

  for _ in range(m):
    edges.append(list(map(int, input().rstrip().split())))

  countPaths(nodes, edges)

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {
    private static int MODULUS = 1000000000;

    /*
     * Complete the 'countPaths' function below.
     *
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. 2D_INTEGER_ARRAY edges
     */

    public static void countPaths(int n, List<List<Integer>> edges) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            adjacency.get(edge.get(0) - 1).add(edge.get(1) - 1);
        }

        long paths = countPaths(0, n - 1, adjacency, new boolean[n], new HashMap<>());

        if (paths == -1) {
            System.out.println("INFINITE PATHS");
        } else {
            System.out.println("" + paths);
        }
    }

    private static long countPaths(int city, int destination, List<List<Integer>> adjacency, boolean[] visited, Map<Integer, Long> memos) {
        if (city == destination) {
            return 1;
        } else if (visited[city]) {
            return -2;
        } else if (memos.containsKey(city)) {
            return memos.get(city);
        }

        visited[city] = true;

        long total = 0;
        boolean looped = false;
        for (int next : adjacency.get(city)) {
            long temp = countPaths(next, destination, adjacency, visited, memos);
            if (temp == -1) {
                return -1;
            } else if (temp == -2) {
                looped = true;
            } else {
                total = (total + temp) % MODULUS;
            }

            if (looped && total > 0) {
                return -1;
            }
        }

        visited[city] = false;
        memos.put(city, total);

        return total;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\s+$", "").split(" ");

        int nodes = Integer.parseInt(firstMultipleInput[0]);

        int m = Integer.parseInt(firstMultipleInput[1]);

        List<List<Integer>> edges = new ArrayList<>();

        IntStream.range(0, m).forEach(i -> {
            try {
                edges.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        Result.countPaths(nodes, edges);

        bufferedReader.close();
    }
}

Problem solution in C++.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cctype>
#include <numeric>
#include <queue>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <iterator>
#define FOR(i,s,e) for(int i=(s);i<(int)(e);i++)
#define FOE(i,s,e) for(int i=(s);i<=(int)(e);i++)
#define ALL(x) (x).begin(), (x).end()
#define CLR(s) memset(s,0,sizeof(s))
#define PB push_back
#define ITER(v)      __typeof((v).begin())
#define FOREACH(i,v) for(ITER(v) i=(v).begin();i!=(v).end();i++)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int> vi;
#define x first
#define y second

const int N = 203600;
vi adj[N];
vi bck[N];

int n, m;

void ae(int x, int y) {
        adj[x].PB(y);
        bck[y].PB(x);
}

vi arr;
bool vis[N];

void dfs(int x) {
        if (vis[x]) return;
        vis[x] = true;
        FOREACH(it, adj[x])
                dfs(*it);
        arr.PB(x); // finishing time
}

int id[N], num;
vi vec[N];

void dfs2(int x) {
        if (vis[x]) return;
        vis[x] = true;
        FOREACH(it, bck[x])
                dfs2(*it);
        id[x] = num;
        vec[num].PB( x );
}

void DAG(int n) {
        CLR(vis);
        FOE(i, 1, n) dfs(i);

        // reversed finishing time
        reverse(ALL(arr));
        CLR(vis);
        num = 0;
        FOREACH(it, arr) if (!vis[*it]) {
                dfs2(*it);
                num++;
        }
}

int dp[N];
int INF = 1999999999;
int MOD = 1000000000;

bool rch[N]; // reachable from 1?

void flood(int x) {
        if (rch[x]) return;
        rch[x] = true;
        FOREACH(it, adj[x]) flood(*it);
}


int go(int x) {
        int &res = dp[x];
        if (res != -1) return res;

//      if (x == 1) return res = 1;
//      if (vec[ id[x] ].size() > 1) return res = INF;

//      if (vec[ id[x] ].size() > 1) return res = INF;
        if (vec[ id[x] ].size() > 1) return res = INF*rch[x];
        if (x == 1) return res = 1;

        res = 0;
        FOREACH(it, bck[x]) {
                int tmp = go(*it);
                if (tmp == INF) return res = INF;
                (res += tmp) %= MOD;
        }

        return res;
}

int main() {
        cin >> n >> m;

        while (m--) {
                int x, y;
                cin >> x >> y;
                ae(x, y);
        }

        DAG(n);

        CLR(rch);
        flood(1);

        memset(dp, -1, sizeof(dp));
        int ans = go(n);

        if (ans == INF) cout << "INFINITE PATHS" << endl;
        else cout << ans << endl;

        return 0;
}

Problem solution in C.

#include <stdio.h>
#define MAX_NODE 10001

#define MOD 1000000000
struct node
{
    unsigned long val;
    char c;
    short lind;
    short rind;
    struct node* links[3000];
    struct node* revlinks[3000];
};

#define  node struct node

int top=-1;

int N,M,ret = 0;//,stack[MAX_NODE];
node* stack[MAX_NODE];

//short visited[MAX_NODE] = {0};
node nodes[MAX_NODE];

void push(node* item)
{
    top = top+1;
    stack[top]=item;
}

node* s_top()
{
    node* deldata=stack[top];
    return(deldata);
}
node* pop()
{
    node* deldata =stack[top];
    top=top-1;
    return(deldata);
}

int is_stk_empty()
{
    if(top==-1)
        return(1);
    else
        return(0);
}


////////////Stack Operation

int cnt = 0;
void dfs1(int n)
{
    int i;
    node* ptr;// ind;
    push(&nodes[1]); //Push starting node into stack.
    
    while(is_stk_empty()!= 1)
    {
        ptr = pop();
        ptr->c = 1;
        
        for (i = 0;i<ptr->lind;i++)
        {
            node* p = ptr->links[i];
            if(p->c != 1)
                push( p);
        }
    }
}

unsigned long dfs(node* ptr)
{
    int i;
    unsigned long retval = 0;
    ptr->c = 2;
    for (i = 0;i < ptr->rind;i++)
    {
        node* p = ptr->revlinks[i];
        if(p  == &nodes[1])
        {
            ptr->val++;
            ptr->val %= MOD;
//            continue;
        }
        
        if(p->c == 1)
        {
            retval = dfs(p);
        }
        else if(p->c == 3)
        {
            retval = p->val;
        }
        else if(p->c == 2)
        {
            printf("INFINITE PATHSn");
            ret = -1;
            return 0;
        }
        
        
        if(ret < 0)
            return 0;
        retval %= MOD;
        ptr->val += retval;
        
        ptr->val %= MOD;
        retval = 0;
    }
    
    ptr->c = 3;
    return ptr->val;
}

int main()
{
    int i;
    scanf("%d%d",&N,&M);
    
    for (i = 0; i< M;i++)
    {
        int j,k;
        scanf("%d%d",&j,&k);
        //nodes[j].vertex = j;
        //nodes[k].vertex = k;
        nodes[j].links[nodes[j].lind++] = &nodes[k];
        nodes[k].revlinks[nodes[k].rind++] = &nodes[j];
    }
    
    dfs1(N);
    top=-1;
    dfs(&nodes[N]);
    if( ret != -1)
        printf("%ld",nodes[N].val);
    
    return 0;
}