All the paths starting from node ‘SRC’ eventually end at node ‘DEST’ if -:

1. Node ‘DEST’ is reachable from ‘SRC’.
2. There is no outgoing edge from node ‘DEST’.
3. No cycle is reachable from ‘SRC’.

We can check these conditions using the Depth First Search algorithm as follows -:

Algorithm

• Create a list of lists ‘ADJ’ of size ‘N’.
• Create an adjacency list of the given directed graph. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][1] in list ADJ[EDGES[i][0]].
• If ADJ[DEST] is not empty, return false as there should be no outgoing edge from node ‘DEST’.
• Created a boolean array/list VISITED  of size ‘N’, initially fill it with false.
• Created a boolean array/list RECSTK  of size ‘N’ to track recursion stack while DFS, initially fill it with false.
• Run a depth-first search algorithm by calling a recursive function, named  DFS(‘CUR’, ‘DEST’, ‘VISITED’,  ‘RECSTK, ‘ADJ’ ). It will return True if all the paths starting from node ‘CUR’ eventually end at node ‘DEST’  In each recursive call of this function, we will do the following steps.
  • If ‘CUR’ = ‘DEST’, then return True.
  • If ‘ADJ[CUR]’ is empty, then return False, because the path ends at a node other than ‘DEST’.
  • Do VISITED[‘CUR’]:= True, and RECSTK[‘CUR’]:= True.
  • Iterate over ADJ[‘CUR’] and for each node ‘V’ in it do the following -:
    • If RECSTK[‘V’] is True then return False, because the cycle is detected.
    • If VISITED[‘V’] is False, then recursively call DFS(‘V’, ‘DEST’, ‘VISITED’ ‘ADJ’ ). Return False, if this recursive call to DFS returns False.
  • Do RECSTK[‘CUR’]:= False, and return True.
• Return  DFS(‘SRC’, ‘DEST’, ‘VISITED’,  ‘RECSTK, ‘ADJ’ ).

O(N + M),  where ‘N’ is the number of nodes and ‘M’ is the number of edges.  

Extra space used by adjacency list ‘ADJ’ is of size O(N + M), and recursion stack, list ‘VISITED’ and ‘RECSTK’  use O(N) space, Thus overall space complexity will be O(N + M). 

O(N + M), where ‘N’ is the number of nodes and ‘M’ is the number of edges.

DFS takes O(N + M) times and creating an adjacency list will also take O(N + M) times, Thus overall time complexity will be O(N + M).

/*

    Time Complexity : O(N + M)

    Space Complexity : O(N + M)



    where 'N' is the number of nodes and 'M' is the number of edges

*/



import java.util.ArrayList;



public class Solution {



    static ArrayListvisited,recStk;



    public static boolean dfs(int cur, int dest,ArrayList> adj) {



        if(cur == dest) {

            return true;

        }



        // Path ends at a node other than Dest

        if(adj.get(cur).size() == 0) {

            return false;

        }



        visited.set(cur,true);

        recStk.set(cur,true);



        for(int i = 0; i < adj.get(cur).size(); i++) {

            // Cycle detected.

            if(recStk.get(adj.get(cur).get(i))) {

                return false;

            }



            if(!visited.get(adj.get(cur).get(i)) && !dfs(adj.get(cur).get(i), dest, adj)) {

                return false;

            }

        }



        recStk.set(cur,false);

        return true;

    }



    public static boolean leadsToDestination(int n, int m, int src, int dest, int edges[][]) {



        // Create adjacency list;

        ArrayList>adj=new ArrayList<>();

        for(int i=0;i());



        for(int i = 0; i < m; i++) {

            int u=edges[i][0];

            int v=edges[i][1];



            ArrayListprev=adj.get(u);

            prev.add(v);



            adj.set(u,prev);

        }



        // There should be no outgoing edge from node Destination.

        if(adj.get(dest).size() != 0) {

            return false;

        }



        visited=new ArrayList<>(n);

        recStk=new ArrayList<>(n);



        for(int i=0;i            visited.add(false);

            recStk.add(false);

        }



        // Run DFS

        return dfs(src, dest, adj);

    }

}

/*



    Time Complexity : O(N + M)

    Space Complexity : O(N + M)



    where ‘N’ is the number of nodes and ‘M’ is the number of edges.



*/



bool dfs(int cur, int dest, vector &visited, vector &recStk, vector> &adj) {

    if(cur == dest) {

        return true;

    }



    // Path ends at a node other than ‘DEST’.

    if(adj[cur].size() == 0) {

        return false;

    }



    visited[cur] = true;

    recStk[cur] = true;



    for(int i = 0; i < adj[cur].size(); i++) {

        // Cycle detected.

        if(recStk[adj[cur][i]] == true) {

            return false;

        }



        if(visited[adj[cur][i]] == false && dfs(adj[cur][i], dest, visited, recStk, adj) == false) {

            return false;

        }

    }



    recStk[cur] = false;

    return true;

}



bool leadsToDestination(int n, int m, int src, int dest, vector> &edges) {

    // Create adjacency list.

    vector> adj(n);

    for(int i = 0; i < m; i++) {

        adj[edges[i][0]].push_back(edges[i][1]);

    }



    // There should be no outgoing edge from node ‘DEST’.

    if(adj[dest].size() != 0) {

        return false;

    }



    vector visited(n), recStk(n);



    // Run DFS.

    return dfs(src, dest, visited, recStk, adj);

}

'''



    Time Complexity : O(N + M)

    Space Complexity : O(N + M)



    where ‘N’ is the number of nodes and ‘M’ is the number of edges.



'''



def dfs(cur, dest, visited, recStk, adj):

    if(cur == dest):

        return True



    # Path ends at a node other than ‘DEST’.

    if(len(adj[cur]) == 0):

        return False



    visited[cur] = True

    recStk[cur] = True



    for i in range(len(adj[cur])):

        # Cycle detected.

        if(recStk[adj[cur][i]] == True):

            return False



        if(visited[adj[cur][i]] == False and dfs(adj[cur][i], dest, visited, recStk, adj) == False):

            return False



    recStk[cur] = False

    return True



def leadsToDestination(n, m, src, dest, edges):

    # Create adjacency list.

    adj = [[] for i in range(n)]

    for i in range(m):

        adj[edges[i][0]].append(edges[i][1])



    # There should be no outgoing edge from node ‘DEST’.

    if(len(adj[dest]) != 0):

        return False



    visited, recStk = [False] * n, [False] * n



    # Run DFS.

    return dfs(src, dest, visited, recStk, adj)