package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 1377. Frog Position After T Seconds
 *
 * 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.
 * */
public class _1377 {
    public static class Solution1 {
        /**credit: https://leetcode.com/problems/frog-position-after-t-seconds/discuss/532505/Java-Straightforward-BFS-Clean-code-O(N)*/
        public double frogPosition(int n, int[][] edges, int t, int target) {
            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                graph[edge[0] - 1].add(edge[1] - 1);
                graph[edge[1] - 1].add(edge[0] - 1);
            }
            boolean[] visited = new boolean[n];
            visited[0] = true;
            double[] probabilities = new double[n];
            probabilities[0] = 1f;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            while (!queue.isEmpty() && t-- > 0) {
                for (int i = queue.size(); i > 0; i--) {
                    int vertex = queue.poll();
                    int nextVerticesCount = 0;
                    for (int next : graph[vertex]) {
                        if (!visited[next]) {
                            nextVerticesCount++;
                        }
                    }
                    for (int next : graph[vertex]) {
                        if (!visited[next]) {
                            visited[next] = true;
                            queue.offer(next);
                            probabilities[next] = probabilities[vertex] / nextVerticesCount;
                        }
                    }
                    if (nextVerticesCount > 0) {
                        probabilities[vertex] = 0;
                    }
                }
            }
            return probabilities[target - 1];
        }
    }
}

@@ -186,1927 +186,8 @@
 e;%0A%0A
-/**%0A * 1377. Frog Position After T Seconds%0A *%0A * Given an undirected tree consisting of n vertices numbered from 1 to n.%0A * A frog starts jumping from the vertex 1.%0A * In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected.%0A * The frog can not jump back to a visited vertex.%0A * In case the frog can jump to several vertices it jumps randomly to one of them with the same probability,%0A * otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.%0A * The edges of the undirected tree are given in the array edges, where edges%5Bi%5D = %5Bfromi, toi%5D means that exists an edge connecting directly the vertices fromi and toi.%0A * Return the probability that after t seconds the frog is on the vertex target.%0A *%0A * Example 1:%0A * Input: n = 7, edges = %5B%5B1,2%5D,%5B1,3%5D,%5B1,7%5D,%5B2,4%5D,%5B2,6%5D,%5B3,5%5D%5D, t = 2, target = 4%0A * Output: 0.16666666666666666%0A * Explanation: The figure above shows the given graph.%0A * The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and%0A * then jumping with 1/2 probability to vertex 4 after second 2.%0A * Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.%0A *%0A * Example 2:%0A * Input: n = 7, edges = %5B%5B1,2%5D,%5B1,3%5D,%5B1,7%5D,%5B2,4%5D,%5B2,6%5D,%5B3,5%5D%5D, t = 1, target = 7%0A * Output: 0.3333333333333333%0A * 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.%0A *%0A * Example 3:%0A * Input: n = 7, edges = %5B%5B1,2%5D,%5B1,3%5D,%5B1,7%5D,%5B2,4%5D,%5B2,6%5D,%5B3,5%5D%5D, t = 20, target = 6%0A * Output: 0.16666666666666666%0A *%0A * Constraints:%0A * 1 %3C= n %3C= 100%0A * edges.length == n-1%0A * edges%5Bi%5D.length == 2%0A * 1 %3C= edges%5Bi%5D%5B0%5D, edges%5Bi%5D%5B1%5D %3C= n%0A * 1 %3C= t %3C= 50%0A * 1 %3C= target %3C= n%0A * Answers within 10%5E-5 of the actual value will be accepted as correct.%0A * */%0A
 publ
@@ -250,16 +250,28 @@
      /**
+%0A         * 
 credit: 
@@ -385,16 +385,26 @@
 ode-O(N)
+%0A         
 */%0A     

refactor 1377