Zombies have placed themselves at every junction in Bucharest. Each junction 'i' initially has a presence of ai number of zombies. Every timestep, each zombie randomly chooses one of its neighboring junctions and walks towards it. Each neighboring junction is choosen by the zombie with an equal probability. In order to safegaurd the citizens of Bucharest we need to find out the expected number of zombies at every junction after 'k' timesteps. 

The network of Bucharest is given as an edge list.  

Input Format  

t - the number of test cases. 't' cases follow.
n, m, k - 'n' junctions (nodes) in Bucharest, 'm' roads (edges) and 'k' time steps. 
This is followed by m lines containing 1 edge on each line. Each edge is denoted by 2 integers representing the nodes it connects, which can range from 0 to n-1.  All the edges are bidirectional. A node cannot connect itself. 
This is followed by n lines, where the i^{th} line contains the initial number of Zombies at the location ai.

Output Format 

Output the number of zombies (rounded of to its nearest integer) in the 5 most highly populated junctions after 'k' timesteps.

Constraints 

1<=t<=5

5<=n<=100000

1<=m<= 200000

1<=k<=10000000

1<=ai<=1000

Sample Input  

1

10 18 100

0 8 

0 5 

1 2 

1 5 

2 8 

2 4 

2 5 

2 6 

3 5 

4 8 

4 6 

4 7 

5 8 

5 9 

6 8 

6 9 

7 9 

8 9 

1

1

1

1

1

1

1

1

1

1

Sample Output 

2 2 1 1 1

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Probability


Solutions:
import sys
import os
is_local_run = os.environ.get('COMPUTERNAME') == 'THUNK'

def run_simulation(neighbors_by_node, zombie_count_by_node):

	def compute_incoming_zombies(node):
		return sum([zombie_count_by_node[neighbor] / len(neighbors_by_node[neighbor]) for neighbor in neighbors_by_node[node]])
	new_zombie_counts_by_node = [compute_incoming_zombies(node) for node in range(len(zombie_count_by_node))]
	deltas = [counts[0] - counts[1] for counts in zip(new_zombie_counts_by_node, zombie_count_by_node)]
	is_stabilised = all((abs(delta) < 0.1 for delta in deltas))
	if is_stabilised:
		print(' '.join([str(round(count)) for count in sorted(new_zombie_counts_by_node, reverse=True)[0:5]]))
	else:
		run_simulation(neighbors_by_node, new_zombie_counts_by_node)

def process_test_cases(reader):
	num_test_cases = int(reader.readline())
	for test_case in range(num_test_cases):
		[num_nodes, num_edges, time_steps] = [int(str_val) for str_val in reader.readline().split(' ')]
		neighbors_by_node = [[] for _ in range(num_nodes)]
		for _ in range(num_edges):
			[node1, node2] = [int(str_val) for str_val in reader.readline().split(' ')]
			neighbors_by_node[node1].append(node2)
			neighbors_by_node[node2].append(node1)
		zombie_count_by_node = [int(reader.readline()) for _ in range(num_nodes)]
		run_simulation(neighbors_by_node, zombie_count_by_node)
if is_local_run:
	reader = open('input02.txt')
else:
	reader = sys.stdin
process_test_cases(reader)


import sys
source = sys.stdin
T = int(source.readline())
for _ in range(T):
	[n, m, k] = [int(s) for s in source.readline().split()]
	neighbors = [[] for i in range(n)]
	for _ in range(m):
		[n0, n1] = [int(s) for s in source.readline().split()]
		neighbors[n0].append(n1)
		neighbors[n1].append(n0)
	zombies = [[], []]
	for _ in range(n):
		zombies[0].append(int(source.readline()))
	for t in range(k):
		start = t % 2
		end = (t + 1) % 2
		zombies[end] = [0] * n
		for src in range(n):
			if zombies[start][src] > 0 and len(neighbors[src]) > 0:
				amt = zombies[start][src] / len(neighbors[src])
				for dest in neighbors[src]:
					zombies[end][dest] += amt
		delta = [abs(x - y) for (x, y) in zip(zombies[start], zombies[end])]
		if max(delta) < 0.0001:
			break
	zombies[end].sort(reverse=True)
	print(round(zombies[end][0]), round(zombies[end][1]), round(zombies[end][2]), round(zombies[end][3]), round(zombies[end][4]))


import sys
import os
is_local_run = os.environ.get('COMPUTERNAME') == 'THUNK'

def run_simulation(neighbors_by_node, zombie_count_by_node):

	def compute_incoming_zombies(node):
		return sum([zombie_count_by_node[neighbor] / len(neighbors_by_node[neighbor]) for neighbor in neighbors_by_node[node]])
	new_zombie_counts_by_node = [compute_incoming_zombies(node) for node in range(len(zombie_count_by_node))]
	deltas = [counts[0] - counts[1] for counts in zip(new_zombie_counts_by_node, zombie_count_by_node)]
	is_stabilised = all((abs(delta) < 0.1 for delta in deltas))
	if is_stabilised:
		print(' '.join([str(round(count)) for count in sorted(new_zombie_counts_by_node, reverse=True)[0:5]]))
	else:
		run_simulation(neighbors_by_node, new_zombie_counts_by_node)

def process_test_cases(reader):
	num_test_cases = int(reader.readline())
	for test_case in range(num_test_cases):
		[num_nodes, num_edges, time_steps] = [int(str_val) for str_val in reader.readline().split(' ')]
		neighbors_by_node = [[] for _ in range(num_nodes)]
		for _ in range(num_edges):
			[node1, node2] = [int(str_val) for str_val in reader.readline().split(' ')]
			neighbors_by_node[node1].append(node2)
			neighbors_by_node[node2].append(node1)
		zombie_count_by_node = [int(reader.readline()) for _ in range(num_nodes)]
		run_simulation(neighbors_by_node, zombie_count_by_node)
if is_local_run:
	reader = open('input02.txt')
else:
	reader = sys.stdin
process_test_cases(reader)


import sys
import os
is_local_run = os.environ.get('COMPUTERNAME') == 'THUNK'

def run_simulation(neighbors_by_node, zombie_count_by_node):

	def compute_incoming_zombies(node):
		return sum([zombie_count_by_node[neighbor] / len(neighbors_by_node[neighbor]) for neighbor in neighbors_by_node[node]])
	new_zombie_counts_by_node = [compute_incoming_zombies(node) for node in range(len(zombie_count_by_node))]
	deltas = [counts[0] - counts[1] for counts in zip(new_zombie_counts_by_node, zombie_count_by_node)]
	is_stabilised = all((abs(delta) < 0.1 for delta in deltas))
	if is_stabilised:
		print(' '.join([str(round(count)) for count in sorted(new_zombie_counts_by_node, reverse=True)[0:5]]))
	else:
		run_simulation(neighbors_by_node, new_zombie_counts_by_node)

def process_test_cases(reader):
	num_test_cases = int(reader.readline())
	for test_case in range(num_test_cases):
		[num_nodes, num_edges, time_steps] = [int(str_val) for str_val in reader.readline().split(' ')]
		neighbors_by_node = [[] for _ in range(num_nodes)]
		for _ in range(num_edges):
			[node1, node2] = [int(str_val) for str_val in reader.readline().split(' ')]
			neighbors_by_node[node1].append(node2)
			neighbors_by_node[node2].append(node1)
		zombie_count_by_node = [int(reader.readline()) for _ in range(num_nodes)]
		run_simulation(neighbors_by_node, zombie_count_by_node)
if is_local_run:
	reader = open('input02.txt')
else:
	reader = sys.stdin
process_test_cases(reader)


import sys
import os
is_local_run = os.environ.get('COMPUTERNAME') == 'THUNK'

def run_simulation(neighbors_by_node, zombie_count_by_node):

	def compute_incoming_zombies(node):
		return sum([zombie_count_by_node[neighbor] / len(neighbors_by_node[neighbor]) for neighbor in neighbors_by_node[node]])
	new_zombie_counts_by_node = [compute_incoming_zombies(node) for node in range(len(zombie_count_by_node))]
	deltas = [counts[0] - counts[1] for counts in zip(new_zombie_counts_by_node, zombie_count_by_node)]
	is_stabilised = all((abs(delta) < 0.1 for delta in deltas))
	if is_stabilised:
		print(' '.join([str(round(count)) for count in sorted(new_zombie_counts_by_node, reverse=True)[0:5]]))
	else:
		run_simulation(neighbors_by_node, new_zombie_counts_by_node)

def process_test_cases(reader):
	num_test_cases = int(reader.readline())
	for test_case in range(num_test_cases):
		[num_nodes, num_edges, time_steps] = [int(str_val) for str_val in reader.readline().split(' ')]
		neighbors_by_node = [[] for _ in range(num_nodes)]
		for _ in range(num_edges):
			[node1, node2] = [int(str_val) for str_val in reader.readline().split(' ')]
			neighbors_by_node[node1].append(node2)
			neighbors_by_node[node2].append(node1)
		zombie_count_by_node = [int(reader.readline()) for _ in range(num_nodes)]
		run_simulation(neighbors_by_node, zombie_count_by_node)
if is_local_run:
	reader = open('input02.txt')
else:
	reader = sys.stdin
process_test_cases(reader)