# Question

Formatted question description: https://leetcode.ca/all/1059.html

 1059. All Paths from Source Lead to Destination

Given the edges of a directed graph, and two nodes source and destination of this graph,
determine whether or not all paths starting from source eventually end at destination, that is:

At least one path exists from the source node to the destination node
If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination.
The number of possible paths from source to destination is a finite number.
Return true if and only if all roads from source lead to destination.

Example 1:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Explanation: It is possible to reach and get stuck on both node 1 and node 2.

Example 2:

Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
Output: false
Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
Output: true

Example 4:

Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
Output: false
Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
Example 5:

Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
Output: false
Explanation: There is infinite self-loop at destination node.

Note:
The given graph may have self loops and parallel edges.
The number of nodes n in the graph is between 1 and 10000
The number of edges in the graph is between 0 and 10000
0 <= edges.length <= 10000
edges[i].length == 2
0 <= source <= n - 1
0 <= destination <= n - 1


# Algorithm

There are 2 cases it should return false.

• case 1: it encounters a node that has no outgoing edges, but it is not destination.
• case 2: it has cycle.

Otherwise, it returns true.

Could iterate graph with BFS. When indegree of a node becomes negative, then ther is cycle.

Time Complexity: O(n+e)

• e = edges.length.

Space: O(n+e).

# Code

• public class All_Paths_from_Source_Lead_to_Destination {

class Solution_bfs {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
Set<Integer>[] graph = new Set[n]; // node => set of its next nodes

for (int i = 0; i < n; i++) {
graph[i] = new HashSet<Integer>();
}

int[] inDegrees = new int[n];
for (int[] edge : edges) {
inDegrees[edge]++;
}

while (!q.isEmpty()) {
int cur = q.poll();
if (graph[cur].size() == 0 && cur != destination) {
return false;
}

for (int nei : graph[cur]) {
if (inDegrees[nei] < 0) { // i.e. a cycle
return false;
}

inDegrees[nei]--;

}
}

return true;
}
}

class Solution_dfs {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
Set<Integer> neighbours = graph.getOrDefault(edge, new HashSet<>());
graph.put(edge, neighbours);
}
if (graph.get(destination) != null) return false;
boolean[] isVisited = new boolean[n];
isVisited[source] = true;
return dfs(graph, isVisited, source, destination);
}

private boolean dfs(Map<Integer, Set<Integer>> graph, boolean[] isVisited, int source, int destination) {
if (source == destination) {
return true;
}

Set<Integer> neighbours = graph.getOrDefault(source, new HashSet<>());
if (neighbours.size() == 0) return false;
for (int neib : neighbours) {

if (isVisited[neib]) return false; // cycle spotted

isVisited[neib] = true;
if (!dfs(graph, isVisited, neib, destination)) return false;
isVisited[neib] = false;
}
return true;
}
}
}

############

class Solution {
private List<Integer>[] g;
private int[] f;
private boolean[] vis;
private int k;

public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
vis = new boolean[n];
g = new List[n];
k = destination;
f = new int[n];
Arrays.setAll(g, key -> new ArrayList<>());
for (var e : edges) {
}
return dfs(source);
}

private boolean dfs(int i) {
if (i == k) {
return g[i].isEmpty();
}
if (f[i] != 0) {
return f[i] == 1;
}
if (vis[i] || g[i].isEmpty()) {
return false;
}
vis[i] = true;
for (int j : g[i]) {
if (!dfs(j)) {
f[i] = -1;
return false;
}
}
f[i] = 1;
return true;
}
}

• // OJ: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/
// Time: O(V + E)
// Space: O(V + E)
class Solution {
vector<unordered_set<int>> G;
vector<int> state; // -1 unvisited, 0 visiting, 1 visited
int dest;
bool dfs(int u) {
if (state[u] != -1) return state[u];
if (G[u].empty()) {
return u == dest;
}
state[u] = 0;
for (int v : G[u]) {
if (!dfs(v)) return false;
}
return state[u] = 1;
}
public:
bool leadsToDestination(int n, vector<vector<int>>& E, int source, int dest) {
G.assign(n, {});
state.assign(n, -1);
this->dest = dest;
for (auto &e : E) {
G[e].insert(e);
}
return dfs(source);
}
};

• class Solution:
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
@cache
def dfs(i):
if i == destination:
return not g[i]
if i in vis or not g[i]: # not g[i]: not destination but no more neigbours
return False
for j in g[i]:
if not dfs(j):
return False
return True

g = defaultdict(list)
for a, b in edges:
g[a].append(b)
vis = set()
return dfs(source)


• func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
vis := make([]bool, n)
g := make([][]int, n)
f := make([]int, n)
for _, e := range edges {
g[e] = append(g[e], e)
}
var dfs func(int) bool
dfs = func(i int) bool {
if i == destination {
return len(g[i]) == 0
}
if f[i] != 0 {
return f[i] == 1
}
if vis[i] || len(g[i]) == 0 {
return false
}
vis[i] = true
for _, j := range g[i] {
if !dfs(j) {
f[i] = -1
return false
}
}
f[i] = 1
return true
}
return dfs(source)
}