Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from the vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices it jumps randomly to one of them with the same probability, otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex. 
The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi.
Return the probability that after t seconds the frog is on the vertex target.
 
Example 1:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 0.16666666666666666 
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666. 

Example 2:

Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 0.3333333333333333
Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1. 

Example 3:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
Output: 0.16666666666666666

 
Constraints:

1 <= n <= 100
edges.length == n-1
edges[i].length == 2
1 <= edges[i][0], edges[i][1] <= n
1 <= t <= 50
1 <= target <= n
Answers within 10^-5 of the actual value will be accepted as correct.

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Graph algorithms

Graph traversal

Starter code: class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        

Solutions:
class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		tree = dict()
		for (i, j) in edges:
			if i > j:
				(i, j) = (j, i)
			tree.setdefault(i - 1, []).append(j - 1)
		(queue, time) = ([(0, 1)], 0)
		while queue and time <= t:
			tmp = []
			for (node, prob) in queue:
				if node == target - 1:
					return 0 if time < t and node in tree else prob
				for n in tree.get(node, []):
					tmp.append((n, prob / len(tree[node])))
			(queue, time) = (tmp, time + 1)
		return 0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		to_edges = defaultdict(list)
		for [so, ta] in edges:
			to_edges[so].append(ta)
			to_edges[ta].append(so)
		to_edges[1].append(1)
		queue = deque([(1, 0, 1)])
		visited = {1}
		while queue:
			(node, time, frac) = queue.popleft()
			if node == target:
				if time == t or (time < t and len(to_edges[node]) == 1):
					return 1 / frac
			if time > t:
				return 0
			for nei in to_edges[node]:
				if nei not in visited:
					queue.append((nei, time + 1, frac * (len(to_edges[node]) - 1)))
					visited.add(nei)
		return 0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		ans = None
		graph = defaultdict(set)
		for (x, y) in edges:
			graph[x].add(y)
			graph[y].add(x)
		vis = set([1])

		def dfs(root, prev_prob, t):
			nonlocal ans
			if t < 0:
				return
			can = graph[root] - vis
			if root == target:
				ans = prev_prob if not can or t == 0 else 0
				return
			for x in can:
				if x not in vis:
					vis.add(x)
					dfs(x, prev_prob * 1.0 / len(can), t - 1)
				if ans is not None:
					return
		dfs(1, 1, t)
		return 0 if ans is None else ans


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = collections.defaultdict(set)
		for (u, v) in edges:
			graph[u].add(v)
			graph[v].add(u)
		seen = set([1])
		queue = collections.deque([(1, 1)])
		while t > 0:
			size = len(queue)
			for _ in range(size):
				(f, prob) = queue.popleft()
				length = 0
				for nb in graph[f]:
					if nb not in seen:
						length += 1
				if length == 0:
					queue.append((f, prob))
				else:
					for nb in graph[f]:
						if nb not in seen:
							seen.add(nb)
							queue.append((nb, prob / length))
			t -= 1
		res = 0
		for (node, prob) in queue:
			if node == target:
				res += prob
		return res


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		if n == 1:
			return 1.0
		graph = collections.defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		q = collections.deque()
		q.append((1, 1.0))
		visited = set()
		self.target = target
		return self.dfs(graph, 1, t, visited)

	def dfs(self, graph, i, t, visited):
		if t == 0 or (i != 1 and len(graph[i]) == 1):
			if i == self.target:
				return 1
			return 0
		result = 0
		visited.add(i)
		for j in graph[i]:
			if j not in visited:
				result += self.dfs(graph, j, t - 1, visited)
		if i == 1:
			return result / len(graph[i])
		else:
			return result / (len(graph[i]) - 1)


import queue
from collections import defaultdict

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		q = queue.Queue()
		graph = defaultdict(list)
		degree = [0] * (n + 1)
		for (f, end) in edges:
			graph[f].append(end)
			graph[end].append(f)
			degree[end] += 1
		start = 1
		visited = set()
		q.put([start, 1, 1])
		visited.add(start)
		res = 0
		qt = 0
		p = [0] * (n + 1)
		p[1] = 1.0
		while t and (not q.empty()):
			qsize = q.qsize()
			for _ in range(qsize):
				(node, level, prob) = q.get()
				size = 0
				for nei in graph[node]:
					if nei not in visited:
						size += 1
				for nei in graph[node]:
					if nei not in visited:
						visited.add(nei)
						q.put([nei, level + 1, prob * (1 / size)])
						p[nei] = p[node] / size
				if size > 0:
					p[node] = 0
			t -= 1
		return p[target]


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = collections.defaultdict(list)
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		q = collections.deque()
		q.append((1, 1.0))
		visited = set()
		visited.add(1)
		step = 0
		while q and step <= t:
			size = len(q)
			for _ in range(size):
				(i, prob) = q.popleft()
				if step == t and i == target:
					return prob
				count = 0
				if i == 1:
					count = len(graph[i])
				else:
					count = len(graph[i]) - 1
				if count == 0:
					q.append((i, prob))
					continue
				for neighbor in graph[i]:
					if neighbor not in visited:
						q.append((neighbor, prob / count))
						visited.add(neighbor)
			step += 1
		return 0.0


from collections import defaultdict
import queue

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		d = defaultdict(set)
		visited = set()
		for edge in edges:
			d[edge[0]].add(edge[1])
			d[edge[1]].add(edge[0])
		q = queue.Queue()
		q.put((1, 0, 1.0))
		visited.add(1)
		goal = {}
		while not q.empty():
			(cur, time, p) = q.get()
			if time > t:
				if target in goal:
					return goal[target]
				return 0.0
			if cur == target and time == t:
				return p
			c = 0
			for adj in d[cur]:
				if adj not in visited:
					c += 1
			if c == 0:
				goal[cur] = p
				continue
			for adj in d[cur]:
				if adj not in visited:
					q.put((adj, time + 1, p / c))
					visited.add(adj)
		if target in goal:
			return goal[target]
		return 0.0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		table = {}
		for i in range(1, n + 1):
			table[i] = []
		for i in range(len(edges)):
			table[edges[i][0]].append(edges[i][1])
			table[edges[i][1]].append(edges[i][0])
		self.res = 0

		def DFS(current_node, p, visited, time):
			if time == t:
				if current_node == target:
					self.res += p
			elif time < t:
				temp = 0
				for node in table[current_node]:
					if node not in visited:
						temp += 1
				if temp > 0:
					for node in table[current_node]:
						if node not in visited:
							temp_visited = visited[:]
							temp_visited.append(node)
							DFS(node, p * 1 / temp, temp_visited, time + 1)
				elif temp == 0:
					DFS(current_node, p, visited, time + 1)
		DFS(1, 1, [1], 0)
		return self.res


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		if not edges:
			return target == 1
		G = defaultdict(list)
		for (s, e) in edges:
			G[s].append(e)
			G[e].append(s)

		def dfs(idx, fr, p, step):
			if step > t:
				return 0
			if idx == target:
				if step == t or (idx != 1 and len(G[idx]) == 1 or (idx == 1 and (not G[idx]))):
					return p
				else:
					return 0
			if idx != 1 and len(G[idx]) == 1:
				return 0
			for nb in G[idx]:
				if nb == fr:
					continue
				ret = dfs(nb, idx, p / (len(G[idx]) - 1 if idx != 1 else len(G[idx])), step + 1)
				if ret:
					return ret
			return 0
		return dfs(1, 0, 1, 0)


def oneJump(edges, visited, target, cur, t):
	if t == 0:
		return 0
	if t == 1 and cur == target:
		return 1
	nxt = []
	visited[cur] = 1
	for i in edges:
		if i[0] == cur and visited[i[1]] == 0:
			nxt.append(i[1])
		elif i[1] == cur and visited[i[0]] == 0:
			nxt.append(i[0])
	if len(nxt) == 0:
		if cur == target:
			return 1
		else:
			return 0
	for i in nxt:
		n = oneJump(edges, visited, target, i, t - 1)
		if n != 0:
			return 1 / len(nxt) * n
	return 0

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		points = [i for i in range(1, n + 1)]
		vis = [0 for i in range(n)]
		visited = dict(zip(points, vis))
		return oneJump(edges, visited, target, 1, t + 1)


from collections import defaultdict, deque

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		nei = collections.defaultdict(set)
		for (a, b) in edges:
			nei[a].add(b)
			nei[b].add(a)
		dp = collections.deque([(1, 1, 0)])
		visited = set()
		while dp:
			(leaf, p, curr) = dp.popleft()
			visited.add(leaf)
			if curr >= t:
				if leaf == target:
					return p
				continue
			neighbors = nei[leaf] - visited
			for n in neighbors or [leaf]:
				dp += ((n, p / (len(neighbors) or 1), curr + 1),)
		return 0.0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		nei = collections.defaultdict(set)
		for (a, b) in edges:
			nei[a].add(b)
			nei[b].add(a)
		(visited, res) = (set(), 0.0)

		def dfs(leaf_id, p, time):
			nonlocal res
			if time >= t:
				if leaf_id == target:
					res = p
				return
			visited.add(leaf_id)
			neighbors = nei[leaf_id] - visited
			for n in neighbors or [leaf_id]:
				dfs(n, p / (len(neighbors) or 1), time + 1)
		dfs(1, 1, 0)
		return res


from collections import defaultdict

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		self.prob = 0
		mp = defaultdict(set)
		for edge in edges:
			mp[edge[0]].add(edge[1])
			mp[edge[1]].add(edge[0])
		visited = set()
		visited.add(1)

		def backtrack(pos: int, nowprob: float, currtime: int, visited: Set[int]):
			if currtime == t:
				if pos == target:
					self.prob += nowprob
				return
			total_visited = 0
			for edge in mp[pos]:
				if edge in visited:
					total_visited += 1
			div = len(mp[pos]) - total_visited
			if div == 0:
				if pos == target:
					self.prob += nowprob
				return
			for edge in mp[pos]:
				if edge not in visited:
					visited.add(edge)
					backtrack(edge, nowprob / div, currtime + 1, visited)
					visited.remove(edge)
		backtrack(1, 1, 0, visited)
		return self.prob


class Solution:

	def frogPosition(self, n: int, edges, t: int, target: int) -> float:
		nei = collections.defaultdict(set)
		for (i, j) in edges:
			nei[i].add(j)
			nei[j].add(i)
		dp = collections.deque([(1, 1, 0)])
		visited = set()
		while dp:
			(leaf, p, curr) = dp.popleft()
			visited.add(leaf)
			if curr >= t:
				if leaf == target:
					return p
				continue
			neighbors = nei[leaf] - visited
			for n in neighbors or [leaf]:
				dp += ((n, p / (len(neighbors) or 1), curr + 1),)
		return 0.0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = collections.defaultdict(list)
		for (a, b) in edges:
			graph[a].append(b)
			graph[b].append(a)
		q = [(1, 1, 0)]
		seen = set()
		while q:
			(curr, p, time) = q.pop(0)
			if time >= t:
				if curr == target:
					return p
				continue
			seen.add(curr)
			s = 0
			for nei in graph[curr]:
				if nei not in seen:
					s += 1
			if s:
				for nei in graph[curr]:
					if nei not in seen:
						q.append((nei, p / s, time + 1))
			else:
				q.append((curr, p, time + 1))
		return 0.0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		neigh = {}
		for e in edges:
			neigh[e[0]] = neigh.get(e[0], []) + [e[1]]
			neigh[e[1]] = neigh.get(e[1], []) + [e[0]]
		front = [1]
		steps = 0
		p = {i: 0 for i in range(1, n + 1)}
		p[1] = 1
		visited = set([1])
		for steps in range(t):
			q = {}
			for i in p:
				if p[i] != 0:
					if i == 1 and len(neigh.get(i, [])) == 0:
						q[i] = p[i]
					elif len(neigh.get(i, [])) <= 1 and i != 1:
						q[i] = p[i]
					else:
						if i == 1:
							nn = len(neigh.get(i, []))
						else:
							nn = len(neigh.get(i, [])) - 1
						for j in neigh.get(i, []):
							if not j in visited:
								q[j] = p[i] / nn
								visited.add(j)
			p = {i: q.get(i, 0) for i in range(1, n + 1)}
		return p.get(target, 0)


from collections import defaultdict, deque

class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = defaultdict(set)
		for (src, dest) in edges:
			graph[src].add(dest)
			graph[dest].add(src)
		q = deque([[1, 1.0, 0]])
		visited = set()
		while q:
			(node, prob, time_step) = q.popleft()
			visited.add(node)
			if time_step >= t:
				if node == target:
					return prob
				continue
			neighbors = graph[node] - visited
			nxt_prob = prob / max(len(neighbors), 1)
			for child in neighbors or [node]:
				q.append((child, nxt_prob, time_step + 1))
		return 0.0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = {}
		for (x, y) in edges:
			graph[x] = graph.get(x, set())
			graph[x].add(y)
			graph[y] = graph.get(y, set())
			graph[y].add(x)
		queue = [(1, 0, 1)]
		visited = set([1])
		while queue:
			if queue[0][1] == t:
				break
			(node, time, p) = queue.pop(0)
			neis = [x for x in graph.get(node, []) if x not in visited]
			size = len(neis)
			if neis:
				for nei in neis:
					queue.append([nei, time + 1, p * 1 / size])
					visited.add(nei)
			else:
				queue.append((node, time + 1, p * 1))
		while queue:
			(node, t, prob) = queue.pop(0)
			if node == target:
				return prob
		return 0


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		visited = [False for i in range(n + 1)]
		visited[0] = True
		visited[n] = True
		prb = [0 for i in range(n)]
		prb[0] = 1
		edgelists = [[] for i in range(n)]
		for i in edges:
			x = i[0] - 1
			y = i[1] - 1
			edgelists[x].append(y)
			edgelists[y].append(x)
		edgelists[0].append(n)
		curr = [0]
		for _ in range(t):
			nex = []
			print(curr)
			for i in curr:
				occ = False
				for j in edgelists[i]:
					if visited[j] == False:
						occ = True
						nex.append(j)
						prb[j] = prb[i] / (len(edgelists[i]) - 1)
						visited[j] = True
				if occ:
					prb[i] = 0
			curr = nex
		print(prb)
		return prb[target - 1]


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		if n == 1:
			return 1.0
		G = collections.defaultdict(list)
		for (i, j) in edges:
			G[i].append(j)
			G[j].append(i)
		seen = set()

		def probability(idx, t):
			if t == 0:
				return idx == target
			if idx != 1 and len(G[idx]) == 1:
				return idx == target
			seen.add(idx)
			(res, count) = (0, 0)
			for j in G[idx]:
				if not j in seen:
					res += probability(j, t - 1)
					count += 1
			return res / count
		return probability(1, t)


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		neighbors = defaultdict(list)
		for (u, v) in edges:
			neighbors[u].append(v)
			neighbors[v].append(u)

		def dfs(u, tt, r):
			if tt > t or u in visited:
				return 0
			if u == target:
				if len(neighbors[u]) > (0 if r else 1) and tt < t:
					return 0
				else:
					return 1
			visited.add(u)
			m = 0
			for v in neighbors[u]:
				m = max(m, dfs(v, tt + 1, False))
			visited.remove(u)
			if r and neighbors[u]:
				return m / len(neighbors[u])
			elif not r and len(neighbors[u]) > 1:
				return m / (len(neighbors[u]) - 1)
			else:
				return 0
		visited = set()
		return dfs(1, 0, True)


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		graph = collections.defaultdict(set)
		for (s, e) in edges:
			graph[s].add(e)
			graph[e].add(s)

		def dfs(prev_node: int, seconds_left: int, visited: Set[int]):
			if seconds_left == 0 or prev_node not in graph:
				return int(prev_node == target)
			probability = 0
			n_next_node = 0
			for next_node in graph[prev_node]:
				if next_node not in visited:
					probability += dfs(next_node, seconds_left - 1, set(list(visited) + [prev_node]))
					n_next_node += 1
			if n_next_node == 0:
				return int(prev_node == target)
			if probability > 0:
				probability /= n_next_node
			return probability
		return dfs(prev_node=1, seconds_left=t, visited=())


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		if n == 1:
			return 1.0
		graph = [[] for i in range(n + 1)]
		for (i, j) in edges:
			graph[i] += (j,)
			graph[j] += (i,)
		visited = [0] * (n + 1)

		def dfs(i, t):
			if i != 1 and len(graph[i]) == 1 or t == 0:
				return i == target
			visited[i] = 1
			res = sum((dfs(j, t - 1) for j in graph[i] if not visited[j]))
			return res * 1.0 / (len(graph[i]) - (i != 1))
		return dfs(1, t)


class Solution:

	def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
		tree = {}

		def add_edge(parent, child):
			children = tree.get(parent, [])
			children.append(child)
			tree[parent] = children
		for [a, b] in edges:
			add_edge(a, b)
			add_edge(b, a)
		if n == 1:
			return 1.0
		result = 1.0 if target == 1 else 0.0
		state = [(1, 1.0)]
		visited = set([1])
		for i in range(t):
			new_state = []
			for (node, probability) in state:
				children = [child for child in tree[node] if child not in visited]
				if len(children) == 0:
					if node == target:
						return probability
					continue
				if node == target:
					return 0
				visited.add(node)
				for child in tree[node]:
					new_probability = probability * 1 / len(children)
					if child == target:
						result = new_probability
					new_state.append((child, new_probability))
			state = new_state
		return result