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:
![](https://spcdn.pages.dev/leetcode/problems/1059.All%20Paths%20from%20Source%20Lead%20to%20Destination/images/485_example_1.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/1059.All%20Paths%20from%20Source%20Lead%20to%20Destination/images/485_example_2.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/1059.All%20Paths%20from%20Source%20Lead%20to%20Destination/images/485_example_3.png)
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#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
def leadsToDestination(
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]:
return False
vis.add(i)
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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| 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) {
g[e[0]].add(e[1]);
}
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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)
}
|