Approach Using BFS-Traversal

As the frog always starts from vertex 1, we can from a node to it’s adjacent vertices.
As this is a tree, from the given edges we need to form a adjacency list where every node is associated with it’s adjacent nodes.
We can track the path of the frog with required parameters like below:
- The current node it is standing.
- The time it has left.
- A Boolean that tells that it has visited target vertex or not in it’s path.
- The parent node from where it is coming. It avoids the frog to go to the parent node from the current node.
From the above information of the current instance for the frog we can figure out the answer.
We can call the above four points as a Frog that contain all the required information’s. Then we can create instances of that frog and process them using a Queue.

Below is the implementation of above approach:

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
// Define a class for Frog
class Frog {
public:
    int node;
    int time;
    int parent;
    bool target_visited;
    Frog(int node, int parent, int time, bool target_visited) : node(node), 
  parent(parent), time(time), target_visited(target_visited) {}
};
 
// Function to simulate frog movement
int frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
    // Create an adjacency list for graph representation
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        adj[i] = vector<int>();
    }
 
    // Decrement the target index for indexing purposes
    --target;
 
    // Fill the adjacency list based on the given edges
    for (auto edge : edges) {
        int u = edge[0], v = edge[1];
        --u;
        --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    // Create a queue to process frog instances
    queue<Frog> q;
    q.push(Frog(0, -1, 0, false)); // Start with frog at node 0
 
    while (!q.empty()) {
        Frog curr = q.front();
        q.pop();
 
        // Check if the frog's time is up
        if (curr.time == t) {
            // Check if the frog reaches the target node or already visited it
            if (curr.node == target || curr.target_visited)
                return curr.node + 1; // Return the node number (incremented by 1 as we 
                                      // decremented earlier)
            continue;
        }
 
        int childs = adj[curr.node].size();
        if (curr.node != 0)
            childs--;
 
        // Frog cannot move further, return current node
        if (childs == 0) {
            if (curr.node == target || curr.target_visited)
                return curr.node + 1;
            continue;
        }
 
        // Explore adjacent nodes and enqueue frog instances
        for (int i : adj[curr.node]) {
            if (i == curr.parent)
                continue;
            q.push(Frog(i, curr.node, curr.time + 1, curr.node == target)); // Enqueue new frog 
                                                                            // instance
        }
    }
    return -1; // No frog can reach the target node
}
 
int main() {
    int n, time, target_node;
    n = 7;
    time = 2;
    target_node = 4;
    vector<vector<int>> edges = { { 1, 2 }, { 1, 3 }, { 1, 7 }, { 2, 4 }, { 2, 6 }, { 3, 5 } };
     
    // Function Call
    cout << frogPosition(n, edges, time, target_node) << endl; // Output the result
    return 0;
}

Java

import java.io.*;
import java.util.*;
 
class GFG {
    public static int frogPosition(int n, int[][] edges,
                                   int t, int target)
    {
        // adjacency list with n nodes
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        --target; // decrement target
        // To  make nodes (1 to n) to (0 to n-1)
        // This avoids adj list suitable nodes
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            --u;
            --v;
            // decrement each node
            // connect nodes
            adj[u].add(v);
            adj[v].add(u);
        }
        // Queue to process frog instances
        Queue<Frog> q = new LinkedList<>();
        // initially frog is at node-0
        // parent is no one for node-0
        // as we multiply probability
        // Cross check the initial values with the Frog
        // Constructor frog timer starts from 0 up and until
        // the timer reaches the given t
        q.offer(new Frog(0, -1, 0, false));
 
        // processing frogs
        while (!q.isEmpty()) {
            // current Frog
            Frog curr = q.poll();
 
            // check for the timer
            if (curr.time == t) {
                // check if it is target_node
                // or check if the frog visited
                // target_node in it's path
                // If so return the (curr node + 1)
                // as we decremented the nodes in starting
                if (curr.node == target
                    || curr.target_visited)
                    return curr.node + 1;
                // else timer has ended up
                // this frog instance doesn't
                // make it to reach the target node.
                continue;
            }
            // get the childs of curr_node
            int childs = adj[curr.node].size();
 
            // If it is not the root node(0)
            // we need to decrement childs by 1
            // As we have parent_node as adjacent node
            // in the curr node
            if (curr.node != 0)
                childs--;
 
            // This is the case where frog ca'nt go further
            // node childs to visit
            // It keeps jumping in this node only
            if (childs == 0) {
                // Same target_node condition check as above
                // did
                if (curr.node == target
                    || curr.target_visited)
                    return curr.node + 1;
                // Same condition where this frog instance
                // didn't complete it's task
                continue;
            }
            // If  current node has unvisited childs
            // then proceed and make further instances of
            // frog
            for (int i : adj[curr.node]) {
                // Check for parent node
                // Avoid looping parent --> child --> parent
                // ....
                if (i == curr.parent)
                    continue;
                // Make Frog instance
                // i is the child so make it curr node for
                // frog instance curr.node became parent for
                // i increase the timer by 1 and check
                // for curr node is target or not
                q.offer(new Frog(i, curr.node,
                                 curr.time + 1,
                                 curr.node == target));
            }
        }
        // No frog can result a answer
        // return probability as zero
        // as no frog could visit target_node
        return -1;
    }
    public static void main(String[] args)
    {
 
        int n, time, target_node;
        n = 7;
        time = 2;
        target_node = 4;
        int edges1[][] = { { 1, 2 }, { 1, 3 }, { 1, 7 },
                           { 2, 4 }, { 2, 6 }, { 3, 5 } };
        // Function Call
        System.out.println(
            frogPosition(n, edges1, time, target_node));
 
    }
    public static class Frog {
        int node;
        int time;
        int parent;
        boolean target_visited;
        Frog(int node, int parent, int time,
             boolean target_visited)
        {
            this.node = node;
            this.parent = parent;
            this.time = time;
            this.target_visited = false;
        }
    }
}

Python3

# Python program for the above approach
from collections import deque
 
# Define a class for Frog
class Frog:
    def __init__(self, node, parent, time, target_visited):
        self.node = node
        self.parent = parent
        self.time = time
        self.target_visited = target_visited
 
# Function to simulate frog movement
def frog_position(n, edges, t, target):
    # Create an adjacency list for graph representation
    adj = [[] for _ in range(n)]
 
    # Decrement the target index for indexing purposes
    target -= 1
 
    # Fill the adjacency list based on the given edges
    for edge in edges:
        u, v = edge
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
 
    # Create a queue to process frog instances
    q = deque([Frog(0, -1, 0, False)])  # Start with frog at node 0
 
    while q:
        curr = q.popleft()
 
        # Check if the frog's time is up
        if curr.time == t:
            # Check if the frog reaches the target node or already visited it
            if curr.node == target or curr.target_visited:
                return curr.node + 1  # Return the node number (incremented by
                                      # 1 as we decremented earlier)
            continue
 
        childs = len(adj[curr.node])
        if curr.node != 0:
            childs -= 1
 
        # Frog cannot move further, return the current node
        if childs == 0:
            if curr.node == target or curr.target_visited:
                return curr.node + 1
            continue
 
        # Explore adjacent nodes and enqueue frog instances
        for i in adj[curr.node]:
            if i == curr.parent:
                continue
            q.append(Frog(i, curr.node, curr.time + 1, curr.node == target))  # Enqueue new frog 
                                                                              # instance
 
    return -1  # No frog can reach the target node
 
if __name__ == "__main__":
    n = 7
    time = 2
    target_node = 4
    edges = [[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]]
 
    # Function Call
    print(frog_position(n, edges, time, target_node))  # Output the result
 
# This code is contributed by Susobhan Akhuli

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
// Define a class for Frog
class Frog {
    public int node;
    public int time;
    public int parent;
    public bool target_visited;
 
    public Frog(int node, int parent, int time,
                bool target_visited)
    {
        this.node = node;
        this.parent = parent;
        this.time = time;
        this.target_visited = target_visited;
    }
}
 
class Program {
    // Function to simulate frog movement
    static int FrogPosition(int n, List<List<int> > edges,
                            int t, int target)
    {
        // Create an adjacency list for graph representation
        List<List<int> > adj = new List<List<int> >();
        for (int i = 0; i < n; i++) {
            adj.Add(new List<int>());
        }
 
        // Decrement the target index for indexing purposes
        target--;
 
        // Fill the adjacency list based on the given edges
        foreach(var edge in edges)
        {
            int u = edge[0] - 1;
            int v = edge[1] - 1;
            adj[u].Add(v);
            adj[v].Add(u);
        }
 
        // Create a queue to process frog instances
        Queue<Frog> q = new Queue<Frog>();
        q.Enqueue(new Frog(
            0, -1, 0, false)); // Start with frog at node 0
 
        while (q.Count > 0) {
            Frog curr = q.Dequeue();
 
            // Check if the frog's time is up
            if (curr.time == t) {
                // Check if the frog reaches the target node
                // or already visited it
                if (curr.node == target
                    || curr.target_visited)
                    return curr.node
                        + 1; // Return the node number
                             // (incremented by 1 as we
                             // decremented earlier)
                continue;
            }
 
            int childs = adj[curr.node].Count;
            if (curr.node != 0)
                childs--;
 
            // Frog cannot move further, return current node
            if (childs == 0) {
                if (curr.node == target
                    || curr.target_visited)
                    return curr.node + 1;
                continue;
            }
 
            // Explore adjacent nodes and enqueue frog
            // instances
            foreach(int i in adj[curr.node])
            {
                if (i == curr.parent)
                    continue;
                q.Enqueue(new Frog(
                    i, curr.node, curr.time + 1,
                    curr.node == target)); // Enqueue new
                                           // frog instance
            }
        }
 
        return -1; // No frog can reach the target node
    }
 
    // Main method to test the FrogPosition function
    static void Main()
    {
        int n = 7;
        int time = 2;
        int targetNode = 4;
        List<List<int> > edges = new List<List<int> >{
            new List<int>{ 1, 2 }, new List<int>{ 1, 3 },
            new List<int>{ 1, 7 }, new List<int>{ 2, 4 },
            new List<int>{ 2, 6 }, new List<int>{ 3, 5 }
        };
 
        // Function Call
        Console.WriteLine(
            FrogPosition(n, edges, time,
                         targetNode)); // Output the result
    }
}
 
// This code is contributed by Susobhan Akhuli

Javascript

// Javascript program for the above approach
 
// Define a class for Frog
class Frog {
    constructor(node, parent, time, targetVisited) {
        this.node = node;
        this.parent = parent;
        this.time = time;
        this.targetVisited = targetVisited;
    }
}
 
// Function to simulate frog movement
function frogPosition(n, edges, t, target) {
    // Create an adjacency list for graph representation
    let adj = new Array(n);
    for (let i = 0; i < n; i++) {
        adj[i] = [];
    }
 
    // Decrement the target index for indexing purposes
    target--;
 
    // Fill the adjacency list based on the given edges
    for (let edge of edges) {
        let u = edge[0] - 1;
        let v = edge[1] - 1;
        adj[u].push(v);
        adj[v].push(u);
    }
 
    // Create a queue to process frog instances
    let q = [];
    q.push(new Frog(0, -1, 0, false)); // Start with frog at node 0
 
    while (q.length > 0) {
        let curr = q.shift();
 
        // Check if the frog's time is up
        if (curr.time === t) {
            // Check if the frog reaches the target node or already visited it
            if (curr.node === target || curr.targetVisited)
                return curr.node + 1; // Return the node number (incremented by 1 as we decremented earlier)
            continue;
        }
 
        let childs = adj[curr.node].length;
        if (curr.node !== 0)
            childs--;
 
        // Frog cannot move further, return current node
        if (childs === 0) {
            if (curr.node === target || curr.targetVisited)
                return curr.node + 1;
            continue;
        }
 
        // Explore adjacent nodes and enqueue frog instances
        for (let i of adj[curr.node]) {
            if (i === curr.parent)
                continue;
            q.push(new Frog(i, curr.node, curr.time + 1, curr.node === target)); // Enqueue new frog instance
        }
    }
    return -1; // No frog can reach the target node
}
 
// Main function
let n = 7;
let time = 2;
let targetNode = 4;
let edges = [[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]];
 
// Function Call
console.log(frogPosition(n, edges, time, targetNode)); // Output the result
 
// This code is contributed by Susobhan Akhuli

Output

Time Complexity: O(N + E) where N is the number of nodes and E is number of edges.
Auxiliary space: O(N + E).

Last node at which Frog is standing after t seconds

Given a Tree consists of n (1<=n<=100) vertices numbered from 1 to n. The given tree is rooted at vertex-1 and the tree edges are given in an array of edges. A frog is standing at vertex-1 and a timer t is given to it. Given edges of the undirected tree as array edges, where edges[i] = [u, v] means there is an edge connecting nodes u and v. A valid path of frog jumps can be described as it should visit the given target vertex. Return the last vertex at which the frog is standing after having a valid path of jumps or return -1 if its path is not valid.

It can only jump from a vertex to any unvisited vertex. Frog takes 1 second to jump from any vertex to any vertex. Until the time stops, the frog should move to a possible unvisited vertex
Or if there is no possible vertex to go to, it jumps to the same vertex till the time completes.
Also, there is a target vertex given such that the frog should visit this vertex in its path.

Examples:

Input-: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
Output: 4
Explanation: The Frog starts from node 1 and after 1 second it reaches node 2. Then again after 1 second, it reaches node 4. As the target node is 4, the frog path is valid and it is standing at node 4 after t seconds.

Explanation 1

Input-: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
Output: 7
Explanation: Frog starts from node 1, it goes to node 7 after 1 second. As there is no other node it can visit from node 7, it keeps jumping at node 7 till the t seconds are completed. After t seconds, the frog path is valid as it visited the target node. At last, it starts at node 7 after t seconds.

Explanation 2

Tags:

#BFS #DSA #Graph #BFS #Graph

Approach Using BFS-Traversal

C++

Java

Python3

C#

Javascript

Last node at which Frog is standing after t seconds

Similar Reads