C# accepted, 276ms, using Breadth-First Traversal with a Queue


  • 1
    R
    public int[] FindOrder(int numCourses, int[,] prerequisites)
    {
        HashSet<int> coursesWithoutPrerequisites;
        Dictionary<int, HashSet<int>> parentChildrenDict;
        Dictionary<int, HashSet<int>> childParentsDict;
        BuildRelationDicts(numCourses, prerequisites, 
            out coursesWithoutPrerequisites, out parentChildrenDict, out childParentsDict);
    
        List<int> result = new List<int>();
        if (coursesWithoutPrerequisites.Count > 0)
        {
            Queue<int> q = new Queue<int>(coursesWithoutPrerequisites);
            HashSet<int> visited = new HashSet<int>();
            HashSet<int> enqueueTwice = new HashSet<int>();
            while (q.Count > 0 && visited.Count < numCourses)
            {
                int temp = q.Dequeue();
                if (!visited.Contains(temp))
                {
                    bool isVisitable = IsVisitable(childParentsDict, visited, temp);
                    if (isVisitable)
                    {
                        visited.Add(temp);
                        result.Add(temp);
    
                        // enqueue its children courses
                        if (parentChildrenDict.ContainsKey(temp))
                        {
                            foreach (int child in parentChildrenDict[temp])
                            {
                                q.Enqueue(child);
                            }
                        }
                    }
                    else if (!enqueueTwice.Contains(temp))
                    {
                        // give it a second chance
                        q.Enqueue(temp);
                        enqueueTwice.Add(temp);
                    }
                }
            }
        }
    
        return result.Count == numCourses ? result.ToArray() : new int[0];
    }
    
    private static void BuildRelationDicts(
        int numCourses, int[,] prerequisites, 
        out HashSet<int> coursesWithoutPrerequisites, 
        out Dictionary<int, HashSet<int>> parentChildrenDict, 
        out Dictionary<int, HashSet<int>> childParentsDict)
    {
        coursesWithoutPrerequisites = GetAllCourses(numCourses);
        parentChildrenDict = new Dictionary<int, HashSet<int>>();
        childParentsDict = new Dictionary<int, HashSet<int>>();
    
        int totalRows = prerequisites.GetLength(0);
        for (int i = 0; i < totalRows; i++)
        {
            int course = prerequisites[i, 0];
            int parent = prerequisites[i, 1];
    
            // build dict
            if (!parentChildrenDict.ContainsKey(parent))
            {
                parentChildrenDict.Add(parent, new HashSet<int>());
            }
            parentChildrenDict[parent].Add(course);
    
            // build dict
            if (!childParentsDict.ContainsKey(course))
            {
                childParentsDict.Add(course, new HashSet<int>());
            }
            childParentsDict[course].Add(parent);
    
            // courses without prerequisites
            coursesWithoutPrerequisites.Remove(course);
        }
    }
    
    private static HashSet<int> GetAllCourses(int numCourses)
    {
        HashSet<int> all = new HashSet<int>();
        for (int i = 0; i < numCourses; i++)
        {
            all.Add(i);
        }
        return all;
    }
    
    private static bool IsVisitable(Dictionary<int, HashSet<int>> childParentsDict, HashSet<int> visited, int temp)
    {
        bool isVisitable = true;
        if (childParentsDict.ContainsKey(temp))
        {
            foreach (int parent in childParentsDict[temp])
            {
                if (!visited.Contains(parent))
                {
                    isVisitable = false;
                    break;
                }
            }
        }
        return isVisitable;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.