Wednesday, July 12th

 For Wednesday, we are looking at how to identify safe versus unsafe nodes, or how to identify a cycle in a graph

My first approach was to use Depth First Search, augmented with a set to store ancestors in the search tree.  While DFS is an accepted solution, my implementation exceeded the time limit

vector<vector<int> > g;
    vector<bool> visited;
    vector<bool> leads_to_cycles;

    void dfs(int node, set<int> pathnodes) {
        
        if(pathnodes.find(node) != pathnodes.end() ) {
            set<int>::iterator itr;
            for(itr=pathnodes.begin(); itr!=pathnodes.end(); ++itr) {
                leads_to_cycles[*itr]=true;
            }
            return;
        }
        
        pathnodes.insert(node);
        visited[node]=true;

        vector<int> neighbors = g[node];
        int v;
        for(int i=0; i<neighbors.size(); i++) {
            v=neighbors[i];
            //if(leads_to_cycles[v]==false) {
                dfs(v,pathnodes);
            //}
        }
        return;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {

        g=graph;
        int n=graph.size();
        visited=vector<bool>(n,false);
        leads_to_cycles=vector<bool>(n, false);

        for(int i=0; i<n; i++) {
            if(visited[i]==false) {
                set<int> initpath;
                dfs(i, initpath);
            }
        }

        vector<int> safe;
        for(int u=0; u<n; u++) {
            if(leads_to_cycles[u]==false) {
                safe.push_back(u);
            }
        }
        return safe;

    }

My approach does not distinguish between nodes in a cycle and nodes previously explored.  To do so, one must keep track of both visited nodes (like in normal DFS) as well as nodes within the current call stack, to detect ancestors.

An easier solution is to use Kahn's Topological Sort algorithm. 

The way it applies here is to:

    1.    Reverse the graph, where instead of an original node going from u -> v, in the new graph the directed edge will go v -> u.  Thus all terminal nodes (as defined by the problem) now have an indegree of 0 with the new graph

    2.    Create an array indegree and store the in degree value of each node

    3.    Create a queue, and push all nodes of in degree 0

    4.    Perform a breadth-first search using the queue.  Each node in the queue is a safe node, and is marked as so in an array safe.  Then iterate through the node's neighbors, and decrement each neighbor's indegree. If the new indegree is zero after the increment, add it to the queue, and repeat.

    5.    After the BFS is complete, return all the safe nodes

Pretty straightforward application to the problem.  Much less complicated than DFS