# 1059. All Paths from Source Lead to Destination

## Description

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, 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


Constraints:

• 1 <= n <= 104
• 0 <= edges.length <= 104
• edges.length == 2
• 0 <= ai, bi <= n - 1
• 0 <= source <= n - 1
• 0 <= destination <= n - 1
• The given graph may have self-loops and parallel edges.

## Solutions

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).

• 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;
}
}

//////

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[1]]++;
}

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[0], new HashSet<>());
graph.put(edge[0], 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 {
public:
bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
vector<bool> vis(n);
vector<vector<int>> g(n);
vector<int> f(n);
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
}
function<bool(int)> dfs = [&](int i) {
if (i == destination) {
return g[i].empty();
}
if (f[i]) {
return f[i] == 1;
}
if (vis[i] || g[i].empty()) {
return false;
}
vis[i] = true;
for (int j : g[i]) {
if (!dfs(j)) {
f[i] = -1;
return false;
}
}
f[i] = 1;
return true;
};
return dfs(source);
}
};

• class Solution: # dfs
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)

#########

from collections import defaultdict, deque

class Solution: # bfs
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
# Build the adjacency list representation of the graph
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)

# Handle the case where the destination node has outgoing edges
if graph[destination]:
return False

# Initialize the visited array to keep track of visited nodes during the traversal
visited = [False] * n

# Start the BFS traversal from the source node
queue = deque([source])
visited[source] = True

while queue:
node = queue.popleft()

# Check if the current node has no outgoing edges and is not the destination node
if node != destination and not graph[node]:
return False

# Process the neighbors of the current node
for neighbor in graph[node]:
# If the neighbor has been visited before, it forms a cycle, return False
if visited[neighbor]:
return False

visited[neighbor] = True
queue.append(neighbor)

# Remove the edge to prevent revisiting the same node
graph[node].remove(neighbor)

# Check if all nodes (except the destination) have been visited
# destination node may have outgoing edges in the graph, so exclude it
return all(visited[i] for i in range(n) if i != destination)


• 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[0]] = append(g[e[0]], e[1])
}
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)
}