Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1377.html
1377. Frog Position After T Seconds (Hard)
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 <= 100edges.length == n-1edges[i].length == 21 <= edges[i][0], edges[i][1] <= n1 <= t <= 501 <= target <= n- Answers within
10^-5of the actual value will be accepted as correct.
Related Topics:
Depth-first Search
Solution 1. DFS
Build the tree then try to generate the path from 1 to target.
- If
tis not enough for reachingtarget, i.e.t + 1 < path.size(), then return0 - If
tis too long that the frog jumps further than thetarget, i.e.t + 1 > path.size() && tree[path.back()].size(), then return0. - Otherwise, the answer is
1.0 / kwherekis the product of all the count of branches from the root to the parent oftarget.
// OJ: https://leetcode.com/problems/frog-position-after-t-seconds/
// Time: O(N)
// Space: O(N)
class Solution {
unordered_map<int, vector<int>> g, nei;
bool dfs(int start, int target, vector<int>&path) {
path.push_back(start);
if (start == target) return true;
for (int n : g[start]) {
if (dfs(n, target, path)) return true;
}
path.pop_back();
return false;
}
void buildTree(int start, int p) {
for (int n : nei[start]) {
if (n == p) continue;
g[start].push_back(n);
buildTree(n, start);
}
}
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
for (auto & e : edges) {
nei[e[0]].push_back(e[1]);
nei[e[1]].push_back(e[0]);
}
buildTree(1, -1);
vector<int> path;
dfs(1, target, path);
if (t + 1 < path.size() || (t + 1 > path.size() && g[path.back()].size())) return 0;
int cnt = 1;
for (int i = 0; i < path.size() - 1; ++i) cnt *= g[path[i]].size();
return 1. / cnt;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/frog-position-after-t-seconds/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/frog-position-after-t-seconds/discuss/532571/Python-DFS
class Solution {
vector<vector<int>> g;
vector<bool> seen;
double dfs(int node, int t, int target) {
seen[node] = true;
int cnt = g[node].size() - (node != 1);
if (!t) return node == target;
if (node == target) return !cnt;
double ans = 0;
for (int n : g[node]) {
if (seen[n]) continue;
if (ans = dfs(n, t - 1, target)) break;
}
if (ans) ans /= cnt;
return ans;
}
public:
double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
g.resize(n + 1);
seen.resize(n + 1);
for (auto &e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
return dfs(1, t, target);
}
};
-
class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { Map<Integer, Set<Integer>> edgesMap = new HashMap<Integer, Set<Integer>>(); for (int[] edge : edges) { int vertex0 = edge[0] - 1, vertex1 = edge[1] - 1; Set<Integer> next0 = edgesMap.getOrDefault(vertex0, new HashSet<Integer>()); next0.add(vertex1); edgesMap.put(vertex0, next0); Set<Integer> next1 = edgesMap.getOrDefault(vertex1, new HashSet<Integer>()); next1.add(vertex0); edgesMap.put(vertex1, next1); } int[] parents = new int[n]; parents[0] = -1; boolean[] visited = new boolean[n]; visited[0] = true; Queue<Integer> bfsQueue = new LinkedList<Integer>(); bfsQueue.offer(0); while (!bfsQueue.isEmpty()) { int vertex = bfsQueue.poll(); Set<Integer> nextVertices = edgesMap.getOrDefault(vertex, new HashSet<Integer>()); for (int nextVertex : nextVertices) { if (!visited[nextVertex]) { visited[nextVertex] = true; parents[nextVertex] = vertex; bfsQueue.offer(nextVertex); } } } int targetPathLength = 0; Set<Integer> targetPathSet = new HashSet<Integer>(); targetPathSet.add(target - 1); int curVertex = target - 1; while (curVertex != 0) { curVertex = parents[curVertex]; targetPathLength++; targetPathSet.add(curVertex); } if (targetPathLength > t) return 0; Map<Integer, Set<Integer>> childrenMap = new HashMap<Integer, Set<Integer>>(); for (int i = 0; i < n; i++) { int parent = parents[i]; if (parent >= 0) { Set<Integer> children = childrenMap.getOrDefault(parent, new HashSet<Integer>()); children.add(i); childrenMap.put(parent, children); } } if (targetPathLength < t) { Set<Integer> targetChildren = childrenMap.getOrDefault(target - 1, new HashSet<Integer>()); if (targetChildren.size() > 0) return 0; } double probability = 1.0; Queue<Integer> queue = new LinkedList<Integer>(); queue.offer(0); while (!queue.isEmpty()) { int parent = queue.poll(); Set<Integer> children = childrenMap.getOrDefault(parent, new HashSet<Integer>()); int childrenSize = children.size(); if (childrenSize == 0) break; probability /= childrenSize; children.retainAll(targetPathSet); for (int child : children) { visited[child] = true; queue.offer(child); } } return probability; } } ############ class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { List<Integer>[] g = new List[n + 1]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] e : edges) { int u = e[0], v = e[1]; g[u].add(v); g[v].add(u); } Deque<Pair<Integer, Double>> q = new ArrayDeque<>(); q.offer(new Pair<>(1, 1.0)); boolean[] vis = new boolean[n + 1]; vis[1] = true; while (!q.isEmpty() && t >= 0) { for (int k = q.size(); k > 0; --k) { Pair<Integer, Double> x = q.poll(); int u = x.getKey(); double p = x.getValue(); List<Integer> nxt = new ArrayList<>(); for (int v : g[u]) { if (!vis[v]) { nxt.add(v); vis[v] = true; } } if (u == target && (nxt.isEmpty() || t == 0)) { return p; } for (int v : nxt) { q.offer(new Pair<>(v, p / nxt.size())); } } --t; } return 0; } } -
// OJ: https://leetcode.com/problems/frog-position-after-t-seconds/ // Time: O(N) // Space: O(N) class Solution { unordered_map<int, vector<int>> g, nei; bool dfs(int start, int target, vector<int>&path) { path.push_back(start); if (start == target) return true; for (int n : g[start]) { if (dfs(n, target, path)) return true; } path.pop_back(); return false; } void buildTree(int start, int p) { for (int n : nei[start]) { if (n == p) continue; g[start].push_back(n); buildTree(n, start); } } public: double frogPosition(int n, vector<vector<int>>& edges, int t, int target) { for (auto & e : edges) { nei[e[0]].push_back(e[1]); nei[e[1]].push_back(e[0]); } buildTree(1, -1); vector<int> path; dfs(1, target, path); if (t + 1 < path.size() || (t + 1 > path.size() && g[path.back()].size())) return 0; int cnt = 1; for (int i = 0; i < path.size() - 1; ++i) cnt *= g[path[i]].size(); return 1. / cnt; } }; -
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() nxt = [v for v in g[u] if not vis[v]] if u == target and (not nxt or t == 0): return p for v in nxt: vis[v] = True q.append((v, p / len(nxt))) t -= 1 return 0 -
type pid struct { x int p float64 } func frogPosition(n int, edges [][]int, t int, target int) float64 { g := make([][]int, n+1) for _, e := range edges { u, v := e[0], e[1] g[u] = append(g[u], v) g[v] = append(g[v], u) } q := []pid{pid{1, 1.0} } vis := make([]bool, n+1) vis[1] = true for len(q) > 0 && t >= 0 { for k := len(q); k > 0; k-- { x := q[0] q = q[1:] u, p := x.x, x.p var nxt []int for _, v := range g[u] { if !vis[v] { vis[v] = true nxt = append(nxt, v) } } if u == target && (len(nxt) == 0 || t == 0) { return p } for _, v := range nxt { q = append(q, pid{v, p / float64(len(nxt))}) } } t-- } return 0 }