_1377.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Queue;

publicclass_1377 {
publicstaticclassSolution1 {
/*
 * credit: https://leetcode.com/problems/frog-position-after-t-seconds/discuss/532505/Java-Straightforward-BFS-Clean-code-O(N)
 */
publicdoublefrogPosition(intn, int[][] edges, intt, inttarget) {
List<Integer>[] graph = newArrayList[n];
for (inti = 0; i < n; i++) {
graph[i] = newArrayList<>();
 }
for (int[] edge : edges) {
graph[edge[0] - 1].add(edge[1] - 1);
graph[edge[1] - 1].add(edge[0] - 1);
 }
boolean[] visited = newboolean[n];
visited[0] = true;
double[] probabilities = newdouble[n];
probabilities[0] = 1f;
Queue<Integer> queue = newLinkedList<>();
queue.offer(0);
while (!queue.isEmpty() && t-- > 0) {
for (inti = queue.size(); i > 0; i--) {
intvertex = queue.poll();
intnextVerticesCount = 0;
for (intnext : graph[vertex]) {
if (!visited[next]) {
nextVerticesCount++;
 }
 }
for (intnext : graph[vertex]) {
if (!visited[next]) {
visited[next] = true;
queue.offer(next);
probabilities[next] = probabilities[vertex] / nextVerticesCount;
 }
 }
if (nextVerticesCount > 0) {
probabilities[vertex] = 0;
 }
 }
 }
returnprobabilities[target - 1];
 }
 }
}