Frog Position After T Seconds solution and explanation

def frog_position(n, edges, t, target):
    from collections import defaultdict

    def dfs(node, prob, time, parent):
        if time == t or len(graph[node]) == (1 if node != 1 else 0):
            return prob if node == target else 0.0

        total_prob = 0.0
        num_choices = len(graph[node]) - (1 if node != 1 else 0)
        for nei in graph[node]:
            if nei == parent:
                continue
            total_prob += dfs(nei, prob / num_choices, time + 1, node)
        return total_prob

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    return dfs(1, 1.0, 0, -1)

import java.util.*;

public class Solution {
    static class Node {
        int vertex;
        double probability;
        int time;

        Node(int v, double p, int t) {
            this.vertex = v;
            this.probability = p;
            this.time = t;
        }
    }

    public double frogPosition(int n, int[][] edges, int t, int target) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }

        return dfs(graph, new Node(1, 1.0, 0), new boolean[n + 1], t, target);
    }

    private double dfs(Map<Integer, List<Integer>> graph, Node node, boolean[] visited, int t, int target) {
        if (node.time == t || graph.get(node.vertex).size() == (node.vertex == 1 ? 0 : 1)) {
            return node.vertex == target ? node.probability : 0.0;
        }

        visited[node.vertex] = true;
        double totalProb = 0.0;
        int choices = 0;

        for (Integer neighbor : graph.get(node.vertex)) {
            if (!visited[neighbor]) choices++;
        }

        for (Integer neighbor : graph.get(node.vertex)) {
            if (!visited[neighbor]) {
                totalProb += dfs(graph, new Node(neighbor, node.probability / choices, node.time + 1), visited, t, target);
            }
        }

        visited[node.vertex] = false;
        return totalProb;
    }
}

function frogPosition(n, edges, t, target) {
    const graph = {};
    for (let [a, b] of edges) {
        if (!graph[a]) graph[a] = [];
        if (!graph[b]) graph[b] = [];
        graph[a].push(b);
        graph[b].push(a);
    }

    const queue = [{ node: 1, prob: 1.0, time: 0 }];
    const visited = Array(n + 1).fill(false);
    visited[1] = true;

    while (queue.length > 0) {
        const { node, prob, time } = queue.shift();

        if (time === t || (node !== 1 && graph[node].length === 1)) {
            if (node === target) return prob;
            continue;
        }

        let neighboursCount = 0;
        for (let nei of graph[node]) {
            if (!visited[nei]) neighboursCount++;
        }

        for (let nei of graph[node]) {
            if (!visited[nei]) {
                visited[nei] = true;
                queue.push({ node: nei, prob: prob / neighboursCount, time: time + 1 });
            }
        }
    }

    return 0.0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public double FrogPosition(int n, int[][] edges, int t, int target) {
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            if (!graph.ContainsKey(edge[1])) graph[edge[1]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        var queue = new Queue<(int node, double prob, int time)>();
        queue.Enqueue((1, 1.0, 0));
        var visited = new bool[n + 1];
        visited[1] = true;

        while (queue.Count > 0) {
            var (node, prob, time) = queue.Dequeue();

            if (time == t || (graph[node].Count == 1 && node != 1)) {
                if (node == target) return prob;
                continue;
            }

            int choices = 0;
            foreach (var nei in graph[node]) {
                if (!visited[nei]) choices++;
            }

            foreach (var nei in graph[node]) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    queue.Enqueue((nei, prob / choices, time + 1));
                }
            }
        }

        return 0.0;
    }
}

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>> g(n + 1);
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        queue<pair<int, double>> q{{{1, 1.0}}};
        bool vis[n + 1];
        memset(vis, false, sizeof(vis));
        vis[1] = true;
        for (; q.size() && t >= 0; --t) {
            for (int k = q.size(); k; --k) {
                auto [u, p] = q.front();
                q.pop();
                int cnt = g[u].size() - (u != 1);
                if (u == target) {
                    return cnt * t == 0 ? p : 0;
                }
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push({v, p / cnt});
                    }
                }
            }
        }
        return 0;
    }
};

function frogPosition(n: number, edges: number[][], t: number, target: number): number {
    const g: number[][] = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
        g[v].push(u);
    }
    const q: number[][] = [[1, 1]];
    const vis: boolean[] = Array.from({ length: n + 1 }, () => false);
    vis[1] = true;
    for (; q.length > 0 && t >= 0; --t) {
        for (let k = q.length; k > 0; --k) {
            const [u, p] = q.shift()!;
            const cnt = g[u].length - (u === 1 ? 0 : 1);
            if (u === target) {
                return cnt * t === 0 ? p : 0;
            }
            for (const v of g[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.push([v, p / cnt]);
                }
            }
        }
    }
    return 0;
}

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)
	}
	type pair struct {
		u int
		p float64
	}
	q := []pair{{1, 1}}
	vis := make([]bool, n+1)
	vis[1] = true
	for ; len(q) > 0 && t >= 0; t-- {
		for k := len(q); k > 0; k-- {
			u, p := q[0].u, q[0].p
			q = q[1:]
			cnt := len(g[u])
			if u != 1 {
				cnt--
			}
			if u == target {
				if cnt*t == 0 {
					return p
				}
				return 0
			}
			for _, v := range g[u] {
				if !vis[v] {
					vis[v] = true
					q = append(q, pair{v, p / float64(cnt)})
				}
			}
		}
	}
	return 0
}