Kingdom Connectivity – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Kingdom Connectivity HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int md = 1e+9;
const int MAXN = 10022;
const int MAXM = 100022;
struct sEdge
{
int a, b;
};
int n, m;
int ean[MAXN], ebn[MAXN], ea[MAXM], eb[MAXM];
sEdge e[MAXM];
int q[MAXN], fm[MAXN], d[MAXN];
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d", &n, &m);
int i;
memset(ean, 0, sizeof(ean));
memset(ebn, 0, sizeof(ebn));
for (i = 1; i <= m; i ++)
{
scanf("%d%d", &e[i].a, &e[i].b);
ean[e[i].a] ++;
ebn[e[i].b] ++;
}
ean[n+1] = ebn[n+1] = m;
for (i = 2; i <= n; i ++)
{
ean[i] += ean[i-1];
ebn[i] += ebn[i-1];
}
for (i = 1; i <= m; i ++)
{
ea[ean[e[i].a]--] = i;
eb[ebn[e[i].b]--] = i;
}
ean[n+1] = ean[n];
int z, x, lql, qh, ql = 0;
memset(fm, 0, sizeof(fm));
q[ql++] = 1; fm[1] = 1;
for (qh = 0; qh < ql; qh ++)
{
z = q[qh];
for (i = ean[z] + 1; i <= ean[z+1]; i ++)
{
x = e[ea[i]].b;
if (fm[x] == 0)
{
q[ql++] = x;
fm[x] = 1;
}
}
}
if (fm[n] == 0)
{
printf("0\n");
return 0;
}
ql = 0;
q[ql++] = n; fm[n] ++;
for (qh = 0; qh < ql; qh ++)
{
z = q[qh];
for (i = ebn[z] + 1; i <= ebn[z+1]; i ++)
{
x = e[eb[i]].a;
if (fm[x] == 1)
{
q[ql++] = x;
fm[x] += 1;
}
}
}
memset(d, 0, sizeof(d));
for (i = 1; i <= m; i ++)
if (fm[e[i].a] + fm[e[i].b] == 4 && e[i].a != n)
d[e[i].b] ++;
lql = 0;
for (i = 1; i <= n; i ++)
lql += (fm[i] == 2);
ql = 0;
for (i = 1; i <= n; i ++)
if (fm[i] == 2 && d[i] == 0)
q[ql++] = i;
for (qh = 0; qh < ql; qh ++)
{
z = q[qh];
for (i = ean[z] + 1; i <= ean[z+1]; i ++)
{
x = e[ea[i]].b;
if ((--d[x]) == 0)
q[ql++] = x;
}
}
if (ql != lql)
{
printf("INFINITE PATHS\n");
return 0;
}
memset(fm, 0, sizeof(fm));
fm[1] = 1;
for (qh = 0; qh < ql; qh ++)
{
z = q[qh];
for (i = ean[z] + 1; i <= ean[z+1]; i ++)
{
x = e[ea[i]].b;
fm[x] = fm[x] + fm[z];
if (fm[x] >= md) fm[x] -= md;
}
}
printf("%d\n", fm[n]);
return 0;
}
Java Kingdom Connectivity HackerRank Solution
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;
public class Solution {
BufferedReader in;
PrintWriter out;
StringTokenizer tok = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
public void run() {
try {
long t1 = System.currentTimeMillis();
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
Locale.setDefault(Locale.US);
solve();
in.close();
out.close();
long t2 = System.currentTimeMillis();
System.err.println("Time = " + (t2 - t1));
} catch (Throwable t) {
t.printStackTrace(System.err);
System.exit(-1);
}
}
String readString() throws IOException {
while (!tok.hasMoreTokens()) {
tok = new StringTokenizer(in.readLine());
}
return tok.nextToken();
}
int readInt() throws IOException {
return Integer.parseInt(readString());
}
long readLong() throws IOException {
return Long.parseLong(readString());
}
double readDouble() throws IOException {
return Double.parseDouble(readString());
}
// solution
void invertEdges() {
ArrayList<Edge> edgesContainer = new ArrayList<Edge>(m);
for (int i = 0; i < n; i++) {
for (Edge edge = first[i]; edge != null; edge = edge.next) {
edgesContainer.add(edge);
}
}
Arrays.fill(first, null);
for (int i = 0; i < edgesContainer.size(); i++) {
Edge edge = new Edge(edgesContainer.get(i).b, edgesContainer.get(i).a, first);
}
}
int n;
int m;
Edge[] first;
void dfs(int source, boolean[] visited) {
if (visited[source]) {
return;
}
visited[source] = true;
// out.println("visiting " + source);
for (Edge edge = first[source]; edge != null; edge = edge.next) {
dfs(edge.b, visited);
}
}
long modulo = 1000000000L;
void solve() throws IOException {
n = readInt();
m = readInt();
first = new Edge[n];
for (int i = 0; i < m; i++) {
int a = readInt() - 1;
int b = readInt() - 1;
Edge edge = new Edge(a, b, first);
}
boolean[] visitedA = new boolean[n];
boolean[] visitedB = new boolean[n];
boolean[] importantNode = new boolean[n];
dfs(0, visitedA);
invertEdges();
// out.println("----");
dfs(n - 1, visitedB);
invertEdges();
for (int i = 0; i < n; i++) {
importantNode[i] = visitedA[i] && visitedB[i];
}
int[] counter = new int[n];
long[] f = new long[n];
for (int i = 0; i < n; i++) {
if (importantNode[i]) {
for (Edge edge = first[i]; edge != null; edge = edge.next) {
if (importantNode[edge.b]) {
counter[edge.b]++;
}
}
}
}
f[0] = 1;
counter[0] = 1;
calculateNumberOfPaths(0, n - 1, counter, f);
if (importantNode[n - 1] //if there is a path from 0 to n - 1
&& counter[n - 1] != 0)//then there is a cycle, probably
{
out.println("INFINITE PATHS");
} else {
out.println(f[n - 1]);
}
}
private void calculateNumberOfPaths(int source, int target, int[] counter, long[] f) {
counter[source]--;
if (counter[source] == 0) {
for (Edge edge = first[source]; edge != null; edge = edge.next) {
f[edge.b] = (f[edge.b] + f[edge.a]) % modulo;
calculateNumberOfPaths(edge.b, target, counter, f);
}
}
}
}
class Edge {
int a;
int b;
Edge next;
Edge(int a, int b, Edge[] edgeTable) {
this.a = a;
this.b = b;
next = edgeTable[a];
edgeTable[a] = this;
}
}
Python 3 Kingdom Connectivity HackerRank Solution
#! /usr/bin/python3
import sys
import copy
N, M = (int(i) for i in input().split())
def add_to_graph(graph, edge):
start, end = edge
if start not in graph:
graph[start] = {}
if end not in graph[start]:
graph[start][end] = 1
else:
graph[start][end] += 1
def print_graph(graph):
for i in sorted(graph.keys(), key=int):
print(i, ":", *list(graph[i].keys()))
graph = {}
backward_graph = {}
for line in sys.stdin:
edge = tuple(int(i) for i in line.split())
add_to_graph(graph, edge)
add_to_graph(backward_graph, reversed(edge))
def find_reachable(start, graph):
reachable = set()
working = {start}
while working:
reachable.update(working)
next_working = set()
for node in working:
if node not in graph:
continue
next_working.update({adj for adj in graph[node].keys()
if adj not in reachable})
working = next_working
return reachable
def purge_unreachable(graph, reachable):
for start in list(graph.keys()):
if start not in reachable:
del graph[start]
else:
for end in list(graph[start].keys()):
if end not in reachable:
del graph[start][end]
forward_reachable = find_reachable(1, graph)
backward_reachable = find_reachable(N, backward_graph)
reachable = forward_reachable.intersection(backward_reachable)
purge_unreachable(graph, reachable)
purge_unreachable(backward_graph, reachable)
# check for loops -- Kosaraju's algorithm
# http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
class Pop:
def __repr__(self): return "pop"
pop_token = Pop()
seen = set()
dfs_stack = [1]
visited_stack = []
# Do a depth first search originating from the first node, and
# push nodes onto the visited_stack in the order the search
# visits them. Keep track of seen nodes, avoiding repeats.
while dfs_stack:
cur = dfs_stack[-1]
if cur == pop_token:
dfs_stack.pop()
visiting_node = dfs_stack.pop()
visited_stack.append(visiting_node)
continue
if cur in seen:
dfs_stack.pop()
continue
seen.add(cur)
dfs_stack.append(pop_token)
if cur not in graph:
continue
for child in graph[cur].keys():
if child in seen:
continue
dfs_stack.append(child)
# The visited stack now contains all nodes. Pop out each of them
# in reverse order. For each, see if it can reach any nodes in
# the backwards graph. If so, you have a cycle! If not, remove it
# from the backwards graph and continue.
backward_graph_copy = copy.deepcopy(backward_graph)
while visited_stack:
cur = visited_stack.pop()
if cur in backward_graph_copy:
print("INFINITE PATHS")
exit()
if cur in graph:
for node in graph[cur]:
del backward_graph_copy[node][cur]
if len(backward_graph_copy[node]) == 0:
del backward_graph_copy[node]
# Count the paths to each node. Paths can't propagate out of node
# until all the paths to that node have been counted. Thus we
# track visits and compare against the backwards graph, to see
# when a node is ready to move forward.
working = {1}
weights = {1:1}
visits = {}
while working:
new_working = set()
for node in working:
if node not in graph:
continue
for (adj, count) in graph[node].items():
if adj not in weights:
weights[adj] = 0
weights[adj] += weights[node] * count
if adj not in visits:
visits[adj] = 0
visits[adj] += 1
if visits[adj] == len(backward_graph[adj]):
new_working.add(adj)
working = new_working
answer = weights[N]
print(answer % (10**9))
Python 2 Kingdom Connectivity HackerRank Solution
Modulo = 1000000000
N, M = map(lambda x: int(x), raw_input().split())
cities = [[[],0,False,False,False] for x in xrange(N+1)]
cycleFound = False
for _ in xrange(M):
x, y = map(lambda x: int(x), raw_input().split())
if x == N: continue
cities[y][0].append(x)
cities[1][1] = 1
cities[1][3] = False
def solve(cityNr):
global cycleFound
if cycleFound: return 0
city = cities[cityNr]
if city[4] or city[3]:
city[2] = city[3]
return city[1]
city[3] = True
for cnr in city[0]: city[1] = (city[1] + solve(cnr)) % Modulo
if city[2] and city[1] > 0:
cycleFound = True
city[4] = True
return city[1]
rezult = solve(N)
print rezult if not cycleFound else "INFINITE PATHS"
C Kingdom Connectivity HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <sys/time.h>
struct weight_t
{ unsigned int edge;
int weight;
int level;
} wa[100000], tmp_wa[100000];
#define MOD_VAL 1000000000LL
int n, m;
int i, j, k;
unsigned long tp[10000] = {0};
unsigned long long used_pred[10000/64+1] = {0};
unsigned long long used_succ[10000/64+1] = {0};
unsigned long long queued[10000/64 + 1] = {0};
unsigned long long good[10000/64+1] = {0};
unsigned long long pred_list[10000][10000/64+1] = {{0}};
unsigned long long succ_list[10000][10000/64+1] = {{0}};
unsigned long long bitmap[10000][10000/64+1] = {{0}};
unsigned long long rev_bitmap[10000][10000/64+1] = {{0}};
int level[10000] = {0};
int num_preds[10000] = {0};
unsigned int array[100000];
unsigned int tmp_array[100000];
unsigned int tmp1, tmp2;
int total;
int loop_at_ends=0;
int marked_for_removal[100000];
int num_marked=0;
#define MAX_SIZE 20001
int q[MAX_SIZE];
int f=0, l=0;
#define queue_empty() ( f == l )
int enqueue( int val )
{ q[l] = val;
l = (l+1) % MAX_SIZE;
// limit will never be reached in problem constraints
}
int dequeue( )
{
int tmp = q[f];
f = (f+1) % MAX_SIZE;
return tmp;
}
int remove_edge ( struct weight_t wa[], int m, unsigned int val )
{
int low, high, mid;
low = 0;
high = m - 1;
val = val << 16;
while (low <= high) {
mid = low + (high - low) / 2;
if ( ( wa[mid].edge & 0xffff0000 ) > val ) {
high = mid - 1;
} else if ( ( wa[mid].edge & 0xffff0000 ) < val ) {
low = mid + 1;
} else {
for ( low = mid ; low >= 0 && ( ( wa[low].edge & 0xffff0000) == val ); --low )
{ // wa[low].edge = 0xFFFFFFFF;
marked_for_removal[ num_marked++ ] = low;
}
for ( high = mid+1 ; high < m && ( ( wa[high].edge & 0xffff0000) == val ) ; ++high )
{ // wa[high].edge = 0xFFFFFFFF;
marked_for_removal[ num_marked++ ] = high;
}
return ( high - low - 1 );
}
}
return 0;
}
int bin_search ( struct weight_t wa[], int m, unsigned int val )
{
int low, high, mid;
low = 0;
high = m - 1;
while (low <= high) {
mid = low + (high - low) / 2;
if ( wa[mid].edge > val ) {
high = mid - 1;
} else if ( wa[mid].edge < val ) {
low = mid + 1;
} else {
return wa[mid].weight;
}
}
return 0;
}
void compress( unsigned int array[], struct weight_t wa[], int * p_m )
{ int i, j, new = 1, last_i = -1 ;
for ( i = 0 , j = 0 ; i < *p_m ; ++i )
{
if ( i == *p_m - 1 || array[i] != array[i+1] )
{ wa[j].edge = array[i];
wa[j].weight = i - last_i ;
last_i = i;
++j;
}
}
*p_m = j;
}
void level_merge(struct weight_t wa[], struct weight_t twa[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (wa[left].level <= wa[mid].level)
{
twa[tmp_pos] = wa[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
twa[tmp_pos] = wa[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
twa[tmp_pos] = wa[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
twa[tmp_pos] = wa[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
wa[right] = twa[right];
right = right - 1;
}
}
void re_merge(struct weight_t wa[], struct weight_t twa[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (wa[left].edge <= wa[mid].edge)
{
twa[tmp_pos] = wa[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
twa[tmp_pos] = wa[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
twa[tmp_pos] = wa[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
twa[tmp_pos] = wa[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
wa[right] = twa[right];
right = right - 1;
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
void level_m_sort( struct weight_t wa[], struct weight_t twa[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
level_m_sort(wa, twa, left, mid);
level_m_sort(wa, twa, mid+1, right);
level_merge(wa, twa, left, mid+1, right);
}
}
void re_m_sort( struct weight_t wa[], struct weight_t twa[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
re_m_sort(wa, twa, left, mid);
re_m_sort(wa, twa, mid+1, right);
re_merge(wa, twa, left, mid+1, right);
}
}
void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void level_sort( struct weight_t wa[], struct weight_t twa[], int m)
{
level_m_sort(wa, twa, 0, m - 1);
}
void re_sort( struct weight_t wa[], struct weight_t twa[], int m)
{
re_m_sort(wa, twa, 0, m - 1);
}
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
int main( int argc, char * argv[] )
{
int removed=0;
scanf("%d%d", &n, &m);
for ( i = 0 ; i < m ; ++i )
{
scanf("%d%d", &tmp1, &tmp2);
--tmp1;
--tmp2;
array[i] = ( tmp1 << 16 ) | tmp2;
bitmap[tmp1][tmp2/64] |= ( 1ULL << (tmp2%64) );
rev_bitmap[tmp2][tmp1/64] |= ( 1ULL << (tmp1%64) );
}
mergeSort( array, tmp_array, m );
compress( array, wa, &m );
used_pred[0] |= 1;
enqueue(0);
while ( ! queue_empty() )
{
i = dequeue();
for ( j = 0 ; j < n ; ++j )
{ while ( j < n && ! bitmap[i][j/64] )
j+= ( 64 - j%64 );
if ( j >= n )
break;
if ( bitmap[i][j/64] & ( 1ULL << ( j % 64 ) ) )
{ pred_list[j][i/64] |= (1ULL << (i%64)) ;
for ( k = 0 ; k <= (n-1)/64 ; k++ )
pred_list[j][k] |= pred_list[i][k];
if ( ! ( used_pred[j/64] & (1ULL << (j%64))) )
{
enqueue(j);
used_pred[j/64] |= (1ULL << (j%64));
}
}
}
}
enqueue(n-1);
used_succ[(n-1)/64] |= (1ULL << ((n-1)%64) );
while ( ! queue_empty() )
{
i = dequeue();
for ( j = 0 ; j < n ; ++j )
{ while ( j < n && ! rev_bitmap[i][j/64] )
j+= ( 64 - j%64 );
if ( j >= n )
break;
if ( rev_bitmap[i][j/64] & ( 1ULL << ( j % 64 ) ) )
{ succ_list[j][i/64] |= (1ULL << (i%64)) ;
for ( k = 0 ; k <= (n-1)/64 ; k++ )
succ_list[j][k] |= succ_list[i][k];
if ( ! ( used_succ[j/64] & (1ULL << (j%64))) )
{
enqueue(j);
used_succ[j/64] |= (1ULL << (j%64));
}
}
}
}
good[0] = 1;
good[(n-1)/64] |= 1ULL << ((n-1)%64);
removed = 0;
for ( i = 1 ; i < n-1 ; ++i )
{ if (( pred_list[i][0] & 1) && ( succ_list[i][(n-1)/64] & ( 1ULL << ((n-1)%64) ) ) )
{ if ( ( pred_list[i][i/64] & ( 1ULL << (i%64) ) ) || ( succ_list[i][i/64] & ( 1ULL << (i%64) ) ) )
{ printf("INFINITE PATHS\n");
return 0;
}
good[ i/64 ] |= ( 1ULL << (i%64) );
}
else
{ removed += remove_edge( wa, m, i);
}
}
while ( num_marked )
{ --num_marked;
wa[ marked_for_removal[num_marked] ].edge = 0xFFFFFFFF;
}
re_sort( wa, tmp_wa, m);
m -= removed;
if ( ( pred_list[0][0] & 1) || ( succ_list[n-1][(n-1)/64] & ( 1ULL << ((n-1)%64) ) ) )
{ if ( pred_list[n-1][0] & 1 )
printf("INFINITE PATHS\n");
else
printf("0\n");
return 0;
}
for ( i = 0 ; i < m ; ++i )
++num_preds[ wa[i].edge & 0xFFFF ];
enqueue(0);
memset( queued, 0, sizeof( queued ) );
while ( ! queue_empty() )
{ unsigned long long ret;
i = dequeue();
queued[i/64] &= ~( 1ULL << (i%64) );
for ( j = 0 ; j < n ; ++j )
{ while ( j < n && ! good[j/64] )
j+= ( 64 - j%64 );
if ( j >= n )
break;
if ( ! ( good[j/64] & ( 1ULL << ( j%64) ) ) )
continue;
if ( bitmap[i][j/64] & ( 1ULL << ( j % 64 ) ) )
{ if ( num_preds[j] == 1 )
{ level[j] = level[i]+1;
if ( j != n-1 && ! ( queued[j/64] & ( 1ULL << (j%64) ) ) )
{
enqueue(j);
queued[j/64] |= ( 1ULL << (j%64) );
}
}
else
--num_preds[j];
}
}
}
for ( i = 0 ; i < m ; ++i )
wa[i].level = level[ wa[i].edge >> 16 ];
level_sort( wa, tmp_wa, m);
tp[0] = 1;
for ( i = 0 ; i < m ; ++i )
{ int s, d;
s = wa[i].edge >> 16;
d = wa[i].edge & 0xFFFF;
tp[d] = ( ( ( ( (unsigned long long) tp[s]) * wa[i].weight ) % MOD_VAL ) + (unsigned long long) tp[d] ) % MOD_VAL ;
}
printf("%lu\n", tp[n-1]);
return 0;
}
Leave a comment below
