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