HackerRank Kingdom Connectivity Solution

In this post, we will solve HackerRank Kingdom Connectivity Problem Solution.

It has been a prosperous year for King Charles and he is rapidly expanding his empire. In fact, he recently invaded his neighboring country and set up a new kingdom! This kingdom has many cities connected by one-way roads. To ensure higher connectivity, two cities are sometimes directly linked by more than one road.
In the new kingdom, King Charles has made one of the cities his financial capital and another city his warfare capital. He wants a better connectivity between these two capitals. The connectivity of a pair of cities, a and 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 the same sequence of roads the same number of times.
There are n cities numbered 1 ton 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. Since the number may be large, print the result modulo 10° or
1000000000.
Note: Two roads may connect the same cities, but they are still considered distinct for path connections.
For example, there are n = 5 cities connected by m = 6 roads as shown in the following graph:

There are two direct paths and one cyclic path. Direct paths are 1 →2→4→ 5 and
1 →2→3 and 1 →→2→4→ 5. The cycle 3 →→→ 4 can be repeated any number of times, so there are infinite paths. If the connection 4 →→ 3 did not exist, there would be only the two direct paths.
Function Description
Complete the countPaths function in the editor below. It should print your result, modulo 10° if there are limited paths or INFINITE PATHS if they are unlimited. There is no expected return value.
countPaths has the following parameters:
-n: the integer number of cities

edges: a 2D integer array where edges[i][0] is the source city and edges[i][1] is the destination city for the directed road i

Input Format
The first line contains two integers n and m.
Each of the following m lines contains two space-separated integers that represent source and destination cities for a directed connection.

Sample Input

Sample Input 0

Sample Output 0

HackerRank Kingdom Connectivity Problem Solution

Kingdom Connectivity C Solution

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>

#define MOD_LIMIT 1000000000

typedef struct {
        unsigned int id;
        struct _list *children;
        unsigned int distance;
} graph;

typedef struct _list {
        struct _list *next;
        graph *g;
} list;

typedef enum {
        UNVISITED, VISITED, LOOPED
} status;

static status *visited;            // array of city statuses
static graph **cities;      // array of city pointers
static jmp_buf buf;                // for loops

/* push a graph into a list of graphs */
void push_graph (list **head, graph *g) {
        list *cur;
        if (*head == NULL) {
               cur = *head = malloc(sizeof(list));
        }
        else {
               for (cur = *head; cur->next != NULL; cur = cur->next);
               cur = cur->next = malloc(sizeof(list));
        }
        
        cur->g = g;
        cur->next = NULL;
}

unsigned int find_paths (graph *source, graph *destination) {
        unsigned int retval = 0;
        list *cur;
        
        if (source == destination) {
               /* Awesome, we made it */
               return 1;
        }
        
        if (visited[source->id - 1] == VISITED) {
               /*
                * Loop in graph!
                * Not sure if this city actually leads to destination though.
                * If not then we don't care.
                * Alert earlier paths.
                */
               visited[source->id - 1] = LOOPED;
               return 0;
        }
        
        if (source->distance != -1) {
               /* Already know how many from here */
               return source->distance;
        }
        
        /* Mark that we've gone through this city already */
        visited[source->id - 1] = VISITED;
        
        for (cur = source->children; cur != NULL; cur = cur->next) {
               /* Check how many paths there are for each child city */
               retval = (retval + find_paths(cur->g, destination)) % (MOD_LIMIT);
        }
        
        /* Store for future paths through this city */
        source->distance = retval;
        
        /* Mark that we're done with this city */
        if (visited[source->id - 1] == LOOPED) {
               /* One of the paths led back here! */
               if (retval > 0) {
                       /* There is a loop on the way to the destination! */
                       longjmp(buf, 1);
               }
               
               /* But this city didn't lead to the destination anyway */
        }
        visited[source->id - 1] = UNVISITED;
        
        return (retval);
}

int main() {
        unsigned int n, m, to, from, money, war,i,j;
        unsigned int num_paths;
        
        scanf("%u %u", &n, &m);
        
        cities = malloc(sizeof(graph *) * n);
        visited = malloc(sizeof(status) * n);
        money=1;
        war=n;
        
        for (i=0; i<n; i++) {
               cities[i] = malloc(sizeof(graph));
               cities[i]->id = i+1;
               cities[i]->children = NULL;
               cities[i]->distance = -1;
               visited[i] = UNVISITED;
        }
        
        for (i=0; i<m; i++) {
               scanf("%u %u", &from, &to);
               //printf("--%d--\n",i);
               /* Add node to parent's children */
               push_graph(&(cities[from-1]->children), cities[to-1]);
        }
        
        
        
        if (!(setjmp(buf))) {
               /* Try this */
               num_paths = find_paths(cities[money-1], cities[war-1]);
               printf("%u\n", num_paths);
        }
        else {
               /* If there are infinite paths just print that */
               printf("INFINITE PATHS\n");
        }
        
        return 0;
}

Kingdom Connectivity C++ Solution

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

vector< int > ts;
bool vis[100000];
bool vis2[100000];
int dp[100000];
#define MOD 1000000000
vector< vector< int > > AdjList;

void dfs(int u) {
    if (vis[u])
        return;
    if (vis2[u]) {
        cout << "INFINITE PATHS" << endl;
        exit(0);
    }
    vis[u] = 1;
    vis2[u] = 1;
    for (auto v : AdjList[u])
        dfs(v);
    ts.push_back(u);
    vis2[u] =0;
}

int main() {
    int N, M, x, y;
    cin >> N >> M;
    AdjList.resize(N);
    for (int i = 0; i < M; i++) {
        cin >> x >> y;
        AdjList[x-1].push_back(y-1);
    }
    dfs(0);
    reverse(ts.begin(),ts.end());
    dp[0] = 1;
    for (int i = 0; i < ts.size(); i++) {
        int u = ts[i];
        for (auto v : AdjList[u])
            dp[v] += dp[u], dp[v] %= MOD;
    }
    cout << dp[N-1] << endl;
    return 0;
}

Kingdom Connectivity C Sharp Solution

using System;
using System.IO;
using System.Collections.Generic;

public struct Natural {
	public static readonly Natural Infinity = new Natural(VALUE_INFINITY);
	private const int VALUE_INFINITY = -1;
	private int val;

	public Natural(int val) {
		this.val = val;
	}

	public int Value {
		get { return val; }
	}

	public bool IsInfinity() {
		return val == VALUE_INFINITY;
	}

	public static Natural operator + (Natural n1, Natural n2) {
		if(n1.IsInfinity() || n2.IsInfinity()) return Infinity;
		return n1.val + n2.val;
	}

	public static Natural operator % (Natural n1, Natural n2) {
		return n1.val % n2.val;
	}

	public static bool operator == (Natural n1, Natural n2) {
		return n1.val == n2.val;
	}

	public static bool operator != (Natural n1, Natural n2) {
		return n1.val != n2.val;
	}

	public static implicit operator Natural(int v) {
		return new Natural(v);
	}

	public static implicit operator int(Natural n) {
		return n.val;
	}

	public override string ToString() {
		return val.ToString();
	}
}

public class City {
	public int Id { get; private set; }
	public Natural PathCount { get; set; } // number of paths from this city to warfare capital
	public ICollection<City> Neighbours { get; private set; }

	public City(int id) {
		Id = id;
		PathCount = -2;
		Neighbours = new LinkedList<City>();
	}

	public bool HasValue(){
		return PathCount != -2;
	}

	public void Add(City c) {
		Neighbours.Add(c);
	}

	public static bool operator == (City c1, City c2) {
		return c1.Id == c2.Id;
	}

	public static bool operator != (City c1, City c2) {
		return !(c1 == c2);
	}

	public static implicit operator int(City c) {
		return c.Id;
	}

	public override bool Equals(object o) {
		return (o is City) && (City)o == this;
	}

	public override int GetHashCode(){
		return Id;
	}
}

public class Solution {
	int N, M;
	readonly Natural MOD = 1000000000;
	bool[] visited; 
	bool[] visited2;
	int[] reachabletb;
	Stack<City> visitedCities;
	City[] cities;
	City firstCity, lastCity;

	/**
	 * Test whether not or not it's reachable from city to city to
	 */
	bool IsReachable(City city, City to) {
		if(city == to) return true; // reach the destination city
		if(visited2[city]) return false; // a cycle;
		int result = reachabletb[city];
		if(result == 1) return true;
		else if(result == -1) return false;

		visited2[city] = true;

		bool anyReachable = false;
		foreach(City neighbour in city.Neighbours) {
			bool reachable = IsReachable(neighbour, to);
			if(reachable) {
				anyReachable = true;
				break;
			}
		}

		visited2[city] = false;
		reachabletb[city] = anyReachable ? 1 : -1;
		return anyReachable;
	}

	Natural CountPath(City city) {
		if(city.HasValue()) return city.PathCount;

		if(visited[city]) {
			// a cycle
			foreach(City c in visitedCities) {
				// if any of the city in the cycle can reach warfare capital, then there's infinite path, otherwise 0
				bool reachable = IsReachable(c, lastCity);
				if(reachable) return Natural.Infinity;
				if(c == city) break;
			}
			return 0;
		}

		visited[city] = true;
		visitedCities.Push(city);
		ICollection<City> neighbours = city.Neighbours;

		Natural totalCount = city == lastCity ? 1 : 0;
		foreach(City n in neighbours) {
			totalCount = (totalCount + CountPath(n)) % MOD;
			if(totalCount.IsInfinity()) break;
		}

		visitedCities.Pop();
		visited[city] = false;

		city.PathCount = totalCount;

		return totalCount;
	}


	void Run(TextReader rd) {
		string[] ln = rd.ReadLine().Split(' ');
		N = int.Parse(ln[0]);
		M = int.Parse(ln[1]);
		visited = new bool[N + 1];
		visited2 = new bool[N + 1];
		visitedCities = new Stack<City>(N);
		cities = new City[N + 1];
		reachabletb = new int[N + 1];

		for(int i = N; i > 0; i--) {
			City c = new City(i);
			cities[i] = c;
		}

		firstCity = cities[1];
		lastCity = cities[N];

		for(int i = 0; i < M; i++) {
			ln = rd.ReadLine().Split(' ');
			int from = int.Parse(ln[0]);
			int to = int.Parse(ln[1]);
			cities[from].Add(cities[to]);
		}

		rd.Dispose();

		Natural count = CountPath(firstCity);

		if(count.IsInfinity()) {
			Console.WriteLine("INFINITE PATHS");
		} else {
			Console.WriteLine(count);
		}
	}

	public static void Main(string[] args) {
		TextReader rd = Console.In;
		new Solution().Run(rd);
	}
}

Kingdom Connectivity Java Solution

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

Kingdom Connectivity Javascript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function visit(i, fromOne, graph) {
    fromOne[i] = 1;
    for (let j = 0; j < graph[i].length; ++j) {
        let next = graph[i][j];
        if (fromOne[next]) {
            continue;
        }
        visit(next, fromOne, graph);
    }
}

function topSort(i, sorted, last, iGraph, valid) {
    sorted[i] = -1;
    for (let j = 0; j < iGraph[i].length; ++j) {
        let next = iGraph[i][j];
        if (!valid[next] || sorted[next] > 0) {
            continue;
        }
        if (sorted[next] == -1) {
            return 1;
        }
        let failed = topSort(next, sorted, last, iGraph, valid);
        if (failed) {
            return 1;
        }
    }
    last[0] = last[0] + 1;
    sorted[i] = last[0];
    return 0;
}

function countPaths(n, edges) {
    // Write your code here
    let iGraph = {};
    let graph = {};
    let fromOne = {};
    let toLast = {};
    for (let i = 1; i <= n; ++i) {
        graph[i] = [];
        iGraph[i] = [];
        fromOne[i] = 0;
        toLast[i] = 0;
    }
    for (let i = 0; i < edges.length; ++i) {
        graph[edges[i][0]].push(edges[i][1]);
        iGraph[edges[i][1]].push(edges[i][0]);
    }
    visit(1, fromOne, graph);
    visit(n, toLast, iGraph);
    let valid = {};
    let sorted = {};
    let last = [0];
    for (let i = 1; i <= n; ++i) {
        valid[i] = fromOne[i] && toLast[i];
        sorted[i] = 0;
    }
    if (!valid[1] || !valid[n]) {
        return 0;
    }
    let failed = topSort(n, sorted, last, iGraph, valid);
    if (failed) {
        return "INFINITE PATHS";
    }
    let topSorted = {};
    let count = {};
    for (let i = 1; i <= n; ++i) {
        if (!valid[i]) {
            continue;
        }
        topSorted[sorted[i]] = i;
        count[i] = 0;
    }
    count[1] = 1;
    //console.log(sorted, topSorted);
    for (let i = 1; i <= last[0]; ++i) {
        let cur = topSorted[i];
        //console.log('visiting', cur);
        for (let j = 0; j < graph[cur].length; ++j) {
            let next = graph[cur][j];
            count[next] += count[cur];
            count[next] %= 1000000000;
            //console.log('incrementing', next, 'by', count[cur]);
        }
    }
    return count[n];
}

function main() {
    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const nodes = parseInt(firstMultipleInput[0], 10);

    const m = parseInt(firstMultipleInput[1], 10);

    let edges = Array(m);

    for (let i = 0; i < m; i++) {
        edges[i] = readLine().replace(/\s+$/g, '').split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
    }

    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
    ws.write(countPaths(nodes, edges) + "\n");
    ws.end();
}

Kingdom Connectivity Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

from collections import defaultdict

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

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited

def triTopo(n,graph,onThePath):
    numero = []
    color = [0 for _ in range(n)]
    for sommet in range(n):
        if sommet in onThePath and color[sommet] == 0:
            if triTopoRec(graph,numero,color,sommet):
                return ([],True)
    return (numero,False)

def triTopoRec(graph,numero,color,sommet):
    color[sommet] = 1
    for voisin in graph[sommet]:
        if color[voisin] == 0:
            if triTopoRec(graph,numero,color,voisin):
                return True
        elif color[voisin] == 1:
            return True
    color[sommet] = 2
    numero.append(sommet)
    return False

def takeSecond(elem):
    return elem[1]

def countPaths(n, edges):
    # Write your code here
    graph = [set() for _ in range(n)]
    graphRevert = [set() for _ in range(n)]
    weight = defaultdict(int)
    for edge in edges:
        i,j = edge
        graph[i].add(j)
        graphRevert[j].add(i)
        weight[(i,j)] += 1

    accessibleFromStart = bfs(graph,0)
    accessibleFromEnd = bfs(graphRevert,n-1)
    onThePath = accessibleFromStart.intersection(accessibleFromEnd)
    
    if not onThePath:
        #No path between start and end
        print(0)
    else:
        newGraph = [set() for _ in range(n)]
        newGraphRevert = [set() for _ in range(n)]
        for edge in edges:
            i,j = edge
            if i in onThePath and j in onThePath:
                newGraph[i].add(j)
                newGraphRevert[j].add(i)
        
        ordre,infinite = triTopo(n,newGraph,onThePath)
        if infinite:
            print("INFINITE PATHS")
        else:
            ordre.reverse()
            nbChemins = [0 for _ in range(n)]
            nbChemins[0] = 1
            for sommet in ordre[1:]:
                for predec in newGraphRevert[sommet]:
                    nbChemins[sommet] += nbChemins[predec] * weight[(predec,sommet)]
            #The end:
            print(nbChemins[n-1]%(10**9))


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(lambda x : int(x)-1, input().rstrip().split())))

    countPaths(nodes, edges)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python