484 ms C++ solutions using topological sort/DFS


  • 0
    L
    bool find_cycle(int *arr,vector<int> *v, int source, vector<int> *topo_sort)
    {
        if(arr[source]==1)
            return true;
    
        int size = v[source].size(), end_vertice;
        int ret_val = false;
        vector<int>::iterator v_itr = v[source].begin();
    
      //  cout << "Processing vertic : " << source << endl;
        arr[source]=1;
    
        while(v_itr!=v[source].end())
        {
            end_vertice = *v_itr;
           // cout << "Pre req ver # " << *v_itr << " with value = " <<arr[end_vertice] << endl;
    
            if(arr[end_vertice]==1)
                return true;
            else if(arr[end_vertice]==0)
            {
                //cout << "Going to other node of req req vertic : " << end_vertice <<endl;
                ret_val = (ret_val || (find_cycle(arr,v,*v_itr,topo_sort)));
            }
            v_itr++;
        }
        arr[source]=2;
        topo_sort->push_back(source);
    
        return ret_val;
    }
    
    vector<int> findOrder(int numCourses, vector<pair<int, int> >& prerequisites)
    {
        int *arr = (int *)malloc(sizeof(int)*numCourses);
        for(int i=0;i<numCourses;i++)
            arr[i] = 0;
    
        // convert the vector into
        vector<int> course_list[numCourses+1];
        vector<pair<int, int> >::iterator pre_itr;
        pair<int,int> temp_pair;
        pre_itr = prerequisites.begin();
    
        int start_ver, dest_ver;
    
        while(pre_itr!= prerequisites.end())
        {
            temp_pair = *pre_itr;
            start_ver = temp_pair.first;
            dest_ver = temp_pair.second;
            course_list[start_ver].push_back(dest_ver);
            pre_itr++;
        }
    
        vector<int> topo_sort;
        vector<int> empty_vector;
        bool cycle_found=false;
    
        for(int i=0;i<numCourses;i++)
            if(arr[i]==0)
                if(find_cycle(arr,course_list,i,&topo_sort))
                    cycle_found=true;
    
        //reverse(topo_sort.begin(),topo_sort.end());
        if(cycle_found)
            return empty_vector;
        else
            return topo_sort;
    }

Log in to reply
 

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