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.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.
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 |
4
Time Complexity: O(N + E) where N is the number of nodes and E is number of edges.
Auxiliary space: O(N + E).