All Paths From Source Lead To Destination Problem Statement

In a directed graph with 'N' nodes numbered from 0 to N-1, determine whether every possible path starting from a given source node (SRC) eventually leads to a specified destination node (DEST). You are provided with a list of edges representing the connections between nodes, along with the node SRC and DEST.

Conditions:

  • There must be at least one path from SRC to DEST.
  • If there's a path from SRC to any node with no outgoing edges, that node should be DEST.
  • The number of paths from SRC to DEST should be finite.

Return True if all paths starting at SRC end at DEST, otherwise return False.

Example:

Input:
 N = 4, EDGES = [[0, 1], [0, 3], [1, 2], [3, 2]], SRC = 0, DEST = 2
Output:
True
Explanation:

All paths originating from node 0 lead to node 2 (DEST) as follows: 0->1->2 and 0->3->2. Since both paths eventually end at the destination node 2, the result is True.

Constraints:

  • 1 <= T <= 50
  • 2 <= N <= 104
  • 0 <= M <= 104
  • 0 <= SRC < N
  • 0 <= DEST < N
  • SRC ≠ DEST
  • 0 <= EDGES[i][j] < N

Input:

 The first line contains the integer 'T', the number of test cases. For each test case: the first line has four space-separated integers: 'N', 'M', 'SRC', 'DEST'. Following are 'M' lines, each with two integers representing a directed edge. 

Output:

 Print 'True' for each test case if every path from SRC leads to DEST, else print 'False'. Each test case result should be on a new line. 

Note:

 No need to print anything. Your task is to implement the function that determines the result. 
AnswerBot
5d

Determine if all paths from a given source node lead to a specified destination node in a directed graph.

  • Check if there is at least one path from source to destination.

  • Ensure that nodes with no outgoi...read more

Help your peers!
Add answer anonymously...
Tredence Senior Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter