This is my solution using bfs+topology sorting, this is based on courseSchedule I.


  • 0
    Y

    public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    //it is just a topological sort
    int[][] matrix=new int[numCourses][numCourses];
    int[] degree= new int[numCourses];

            for(int i=0;i<prerequisites.length;i++)
            {
                int ready=prerequisites[i][0];
                int pre=prerequisites[i][1];
                if(matrix[pre][ready]!=1)
                {
                    matrix[pre][ready]=1;
                    degree[ready]++;
                }
            }
            
            Queue<Integer> q= new LinkedList<Integer>();
            int count=0;
            for(int i=0;i<numCourses;i++)
            {
                if(degree[i]==0)
                {
                    q.offer(i);
                }
            }
            int [] result=new int[numCourses];
            while(!q.isEmpty())
            {
                int curr=q.poll();
                result[count]=curr;
                count++;
                for(int i=0;i<numCourses;i++)
                {
                    if(matrix[curr][i]==1)
                    {
                        degree[i]--;
                        if(degree[i]==0)
                        {
                            q.offer(i);
                        }
                    }
                }
                
            }
            
            if(count==numCourses)
            {
                return result;
            }
            
            else
            {
                return new int[0];
            }
            
            
            
          
    }
    

    }


  • 0
    Y

    based on this one, exactly the same idea just add an extra list to track the path.
    [https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java/24](link url)


Log in to reply
 

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