Tap here to switch tabs
Problem
Submissions

Problem: All Paths from Source Lead to Destination

Try to solve the All Paths from Source Lead to Destination problem.

Statement

Given a directed graph of n nodes labeled from 00 to n −1- 1, represented by a 22D array edges where each edges[i] = [a_i, b_i] denotes a directed edge from node a_i to node b_i, along with two nodes source and destination, determine whether all paths starting from source eventually terminate at destination.

All paths starting from source lead to destination if and only if:

  • At least one path starts from source.

  • Every path starting from source ends at destination.

  • The node destination has no outgoing edges.

  • There is no cycle reachable from source that allows an infinite path.

Return true if all paths starting from source lead to destination, or false otherwise.

Constraints:

  • 1≤1 \leq n ≤104\leq 10^4

  • 0≤0 \leq edges.length ≤104\leq 10^4

  • edges[i].length =2= 2

  • 0≤0 \leq a_i, b_i ≤\leq n −1- 1

  • 0≤0 \leq source ≤\leq n −1- 1

  • 0≤0 \leq destination ≤\leq n −1- 1

  • The given graph may have self loops and parallel edges.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: All Paths from Source Lead to Destination

Try to solve the All Paths from Source Lead to Destination problem.

Statement

Given a directed graph of n nodes labeled from 00 to n −1- 1, represented by a 22D array edges where each edges[i] = [a_i, b_i] denotes a directed edge from node a_i to node b_i, along with two nodes source and destination, determine whether all paths starting from source eventually terminate at destination.

All paths starting from source lead to destination if and only if:

  • At least one path starts from source.

  • Every path starting from source ends at destination.

  • The node destination has no outgoing edges.

  • There is no cycle reachable from source that allows an infinite path.

Return true if all paths starting from source lead to destination, or false otherwise.

Constraints:

  • 1≤1 \leq n ≤104\leq 10^4

  • 0≤0 \leq edges.length ≤104\leq 10^4

  • edges[i].length =2= 2

  • 0≤0 \leq a_i, b_i ≤\leq n −1- 1

  • 0≤0 \leq source ≤\leq n −1- 1

  • 0≤0 \leq destination ≤\leq n −1- 1

  • The given graph may have self loops and parallel edges.