C# implementation using topological sort


  • 0
    S
    public class Solution 
    {
        public int[] FindOrder(int n, int[,] preq) 
        {
            var adj = new List<List<int>>();
            var rem = new int[n];
            
            for(int i = 0; i < n; i++)
                adj.Add(new List<int>());
                
            for(int i = 0; i < preq.GetLength(0); i++)
            {
                int u = preq[i,1];
                int v = preq[i,0];
                adj[u].Add(v);
                rem[v]++;
            }
            
            var queue = new Queue<int>();
            var result = new List<int>();
            
            for(int i = 0; i < n; i++)
                if(rem[i] == 0)
                    queue.Enqueue(i);
                    
            while(queue.Count > 0)
            {
                int u = queue.Dequeue();
                result.Add(u);
                
                foreach(int v in adj[u])
                {
                    rem[v]--;
                    if(rem[v] == 0)
                        queue.Enqueue(v);
                }
            }
            
            return result.Count < n ? new int[0] : result.ToArray();
        }
    }
    

Log in to reply
 

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