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.
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
Top Tredence Senior Software Engineer interview questions & answers
Popular interview questions of Senior Software Engineer
Top HR questions asked in Tredence Senior Software Engineer
Reviews
Interviews
Salaries
Users/Month