1059

1059. All Paths from Source Lead to Destination (Medium)

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

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.

 

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.

Companies:
Bloomberg

Related Topics:
Depth-First Search, Graph

Solution 1. Topological Sort (DFS)

// OJ: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/
// Author: github.com/lzl124631x
// 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[0]].insert(e[1]);
        }
        return dfs(source);
    }
};

Solution 2. Topological Sort (BFS)

To make the BFS version work, quite a few modifications were added. The DFS version is easier for this problem.

// OJ: https://leetcode.com/problems/all-paths-from-source-lead-to-destination/
// Author: github.com/lzl124631x
// Time: O(N + E)
// Space: O(N + E)
class Solution {
public:
    bool leadsToDestination(int n, vector<vector<int>>& E, int src, int dest) {
        vector<vector<int>> G(n);
        vector<int> indegree(n), outdegree(n), state(n); // 0 - unvisited, 1 - should be visited, 2 - visited
        for (auto &e : E) {
            int u = e[0], v = e[1];
            G[u].push_back(v);
            ++indegree[v];
            ++outdegree[u];
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) q.push(i);
        }
        state[src] = 1;
        while (q.size()) {
            int u = q.front();
            q.pop();
            if (state[u] == 1) state[u] = 2;
            if (outdegree[u] == 0 && state[u] == 2 && u != dest) return false;
            for (int v : G[u]) {
                if (state[u]) state[v] = 1;
                if (--indegree[v] == 0) q.push(v);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (state[i] == 1) return false;
        }
        return true;
    }
};