# 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:
memo[cur] += inc
memo[cur] %= MOD

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

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

{"mode":"full","isActive":false}

## 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) {
for (int i = 0; i < n; i++) {
}
for (List<Integer> edge : edges) {
}

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

}
}

public class Solution {
public static void main(String[] args) throws IOException {

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 {
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});

Result.countPaths(nodes, edges);

}
}
```

{"mode":"full","isActive":false}

## 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 bck[N];

int n, m;

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

vi arr;
bool vis[N];

void dfs(int x) {
if (vis[x]) return;
vis[x] = true;
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;
}

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

{"mode":"full","isActive":false}

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

#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++)
{
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++)
{
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 PATHS\n");
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;
}

dfs1(N);
top=-1;
dfs(&nodes[N]);
if( ret != -1)
printf("%ld",nodes[N].val);

return 0;
}
```

{"mode":"full","isActive":false}