{x}
blog image

Frog Position After T Seconds

Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from 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] = [ai, bi] means that exists an edge connecting the vertices ai and bi.

Return the probability that after t seconds the frog is on the vertex target. Answers within 10-5 of the actual answer will be accepted.

 

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.

 

Constraints:

  • 1 <= n <= 100
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • 1 <= t <= 50
  • 1 <= target <= n

1377. Frog Position After T Seconds

Problem Description

This problem involves calculating the probability of a frog reaching a target vertex on an undirected tree after a specific number of seconds. The frog starts at vertex 1 and can jump to an unvisited adjacent vertex in each second. If multiple unvisited vertices are available, it jumps to each with equal probability.

Solution: Breadth-First Search (BFS)

The optimal approach uses Breadth-First Search (BFS) to traverse the tree. We maintain a queue to track the frog's position and the probability of reaching that position.

Algorithm:

  1. Graph Representation: Construct an adjacency list to represent the tree. g[u] stores the list of vertices adjacent to vertex u.

  2. Initialization:

    • Create a queue q initially containing (1, 1.0), representing the frog's starting position (vertex 1) and initial probability (1.0).
    • Create a boolean array vis to track visited vertices, initializing vis[1] = true.

  3. BFS Traversal: Iterate while the queue is not empty and the time t is greater than or equal to 0. In each iteration:

    • Process all vertices currently in the queue (the number of vertices equals the len(q) at the beginning of the loop).
    • For each vertex u and probability p dequeued from q:
      • Target Check: If u is the target vertex:
        • If cnt (number of unvisited neighbors) is 0 (frog is stuck) or it's the exact time t, return p. Otherwise, return 0 (frog couldn't reach the target at the exact time).
      • Neighbor Exploration: Otherwise (u is not the target):
        • Calculate cnt the number of unvisited neighbors of u. Adjust cnt by subtracting 1 if u isn't the starting node (to avoid counting the parent in the first step).
        • For each unvisited neighbor v:
          • Mark v as visited (vis[v] = true).
          • Enqueue (v, p / cnt) to q, distributing the probability equally among unvisited neighbors.
    • Decrement t to simulate the passage of time.

  4. Return 0: If the queue becomes empty or t becomes negative before reaching the target, return 0 (frog didn't reach the target).

Time Complexity: O(N), where N is the number of nodes in the tree. BFS visits each node at most once.

Space Complexity: O(N) in the worst case to store the queue and the vis array.

Code Examples (Python)

from collections import defaultdict, deque
 
class Solution:
    def frogPosition(self, n: int, edges: list[list[int]], t: int, target: int) -> float:
        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        q = deque([(1, 1.0)])
        vis = [False] * (n + 1)
        vis[1] = True
        while q and t >= 0:
            for _ in range(len(q)):
                u, p = q.popleft()
                cnt = len(g[u]) - int(u != 1)  # Adjust cnt for starting node
                if u == target:
                    return p if cnt * t == 0 else 0  # Check for stuck or exact time
                for v in g[u]:
                    if not vis[v]:
                        vis[v] = True
                        q.append((v, p / cnt))
            t -= 1
        return 0

The code in other languages (Java, C++, Go, TypeScript, C#) provided in the original response follows the same algorithmic approach, differing only in syntax and data structure implementations. The core logic of BFS and probability distribution remains consistent across all the languages.