LeetCode1059 All Paths From Source Lead to Destination_given the adjacency lists of a directed graph as s

Given the edges of a directed graph, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually end at destination,
this problem is pretty straight forward.

and so is the solution:

class Solution {
    enum State { PROCESSING, PROCESSED } //this is some thing i Never seen before
    
    public boolean leadsToDestination(int n, int[][] edges, int src, int dest) {
        List<Integer>[] graph = buildDigraph(n, edges);
        return leadsToDest(graph, src, dest, new State[n]);
    }
    
    private boolean leadsToDest(List<Integer>[] graph, int node, int dest, State[] states) { //this is the core function which used for check if there is only one way from start to dest
        if (states[node] != null) return states[node] == State.PROCESSED; //if we have meet the node before, then mark it as processed
        if (graph[node].isEmpty()) return node == dest; //if current node is ending node, check if it is the dest node we want
        states[node] = State.PROCESSING;  //if we haven't meet the node before and current node is not a end node either, then we mark it as processing
        for (int next : graph[node]) { //for every neighbor of current node
            if (!leadsToDest(graph, next, dest, states)) return false; //if any of the neighbors can't lead to the destiination, then it's a false, bacause we are equaired to make sure every neighbor lead to the destination.
        }
        states[node] = State.PROCESSED;
        return true;
    }
    
    private List<Integer>[] buildDigraph(int n, int[][] edges) { //use given edges to build a graph, which is [<>,<>,<>]
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]); //due to it is a directed graph, so we only add for once
        }
        return graph;
    }
}
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

so the solution are basically build the graph first, and then use dfs to find if there is a unique valid path from given starting point to destination.

//the second way, pretty same idea:

class Solution {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        // Convert matrix to adjacency list
        Map<Integer, Set<Integer>> adjList = new HashMap<>();
        for (int i = 0; i < edges.length; ++i) {
            adjList.putIfAbsent(edges[i][0], new HashSet<Integer>());
            adjList.get(edges[i][0]).add(edges[i][1]);
        }
        
        // destination node should not have outgoing edge.
        if (adjList.containsKey(destination)) return false; //we ned to make sure that the destination is the ending
        
        return dfs(adjList, source, destination, new boolean[n]);
    }
    
    private boolean dfs(Map<Integer, Set<Integer>> adjList, int source, int destination, boolean[] seen) { //dfs backtracking
        if (source == destination) return true;
        
        seen[source] = true;
        
        // Non-destination node must have outgoing edge, otherwise it is stuck.
        if (!adjList.containsKey(source)) return false;
            
        for (Integer node : adjList.get(source)) //for every neighbor of current node
            if (seen[node] || !dfs(adjList, node, destination, seen)) return false; //if any of it neighbors can't lead to destination, then its a no no, because we need every path must lead to that destination. this statement is the core for the whole problem
        
        seen[source] = false; //backtracking
        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