1059. All Paths from Source Lead to Destination

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.

class Solution {
    vector<int> dp;
    vector<vector<int>> graph;
    int solution(int position) {
        if(dp[position] != -1) return dp[position];
        dp[position] = 0;
        int res = graph[position].empty() ? 0 : 1;
        for(auto next : graph[position]) {
            res &= solution(next);
        }
        return dp[position] = res;
    }
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        dp = vector<int>(n, -1);
        dp[destination] = 1;
        graph = vector<vector<int>>(n,vector<int>());
        
        for(auto edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            if(edge[0] == destination) return false;
        }
        
        return solution(source);
    }
};

class Solution {
    bool dfs(vector<list<int>> &e, vector<int> &visited, int from, int dest) {
        if(e[from].empty()) return from == dest;
        if(visited[from] != -1) return visited[from];
        visited[from] = false;
        for(auto to : e[from]) {
            if(!dfs(e, visited, to, dest)) return false;
        }
        return visited[from] = true;
    }
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<list<int>> e(n, list<int>());
        vector<int> visited(n, -1);
        for(auto edge : edges) {
            if(edge.front() == destination) return false;
            e[edge.front()].push_back(edge.back());
        }
        return dfs(e, visited, source, destination);
    }
};