[Uber][LeetCode] Course Schedule

Problem: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Approach: Basically it's a simple problem of finding a cycle in the Graph which can be achieved by DFS. 

Implementation in C#:

public class GraphNode

{

    public int Value { get; set; }

    public List<GraphNode> Neighbours { get; set; }

    public GraphNode(int val, List<GraphNode> neighbours = null)

    {

        this.Value = val;

        this.Neighbours = neighbours == null ? new List<GraphNode>() : neighbours;

    }

}

public class Graph

{

    public Graph()

    {

        this.nodes = new List<GraphNode>();

        this.nodesMap = new Dictionary<int, GraphNode>();

    }

    

    public void CreateNode(int value)

    {

        var node = new GraphNode(value);

        this.nodes.Add(node);

        this.nodesMap[value] = node;

    }

    

    public void AddNeighbour(int src, int neighbour)

    {

        var srcNode = this.nodesMap[src];

        var neighbourNode = this.nodesMap[neighbour];

        srcNode.Neighbours.Add(neighbourNode);

    }

    

    public bool DoesExistACycle()

    {

        if (this.nodes == null || this.nodes.Count <= 1)

        {

            return false;

        }        

        HashSet<int> visited = new HashSet<int>();

        foreach (var node in this.nodes)

        {

            if (!visited.Contains(node.Value))

            {

                HashSet<int> onCycle = new HashSet<int>();

                if (this.DFSCycle(node, onCycle, visited))

                {

                    return true;

                }

            }

        }

        return false;

    }

    

    private bool DFSCycle (GraphNode node, HashSet<int> onCycle, HashSet<int> visited)

    {

        if (visited.Contains(node.Value))

        {

            return false;

        }

        visited.Add(node.Value);

        onCycle.Add(node.Value);

        foreach (var neighbour in node.Neighbours)

        {

            if (onCycle.Contains(neighbour.Value) || this.DFSCycle(neighbour, onCycle, visited))

            {

                return true;

            }

        }

        onCycle.Remove(node.Value);

        return false;

    }

    

    private List<GraphNode> nodes;

    private Dictionary<int, GraphNode> nodesMap;

}

public class Solution 

{

    public bool CanFinish(int numCourses, int[][] prerequisites) 

    {

        var graph = new Graph();

        this.BuildGraphNodes(graph, numCourses);

        this.AddNeighbours(graph, prerequisites);

        return !graph.DoesExistACycle();

    }

    

    private void BuildGraphNodes(Graph graph, int numCourses)

    {

        for (int i = 0; i < numCourses; ++i)

        {

            graph.CreateNode(i);

        }

    }

    

    private void AddNeighbours(Graph graph, int[][] prerequisites)

    {

        foreach (var prerequisite in prerequisites)

        {

            graph.AddNeighbour(prerequisite[1], prerequisite[0]);

        }

    }

}

Complexity: O(n)