C++ Time(V+E) and Space(V+E) BFS


  • -1
    D
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int takennum=0;
        int count[numCourses];
        queue<int> qu;
        
        for(int i=0;i<numCourses;i++)
            count[i]=0;
        //number of pre
        for(int i=0;i<prerequisites.size();i++)
            count[prerequisites[i][0]]++;
        //edge
        vector<vector<int>> edge(numCourses);
        for(int i=0;i<prerequisites.size();i++)
            edge[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        for(int i=0;i<numCourses;i++)
        {
            if(!count[i])
            {
                takennum++;
                qu.push(i);
            }
        }
        // V+E    
        while(!qu.empty())
        {
            int a=qu.front();
            qu.pop();
            for(int i=0;i<edge[a].size();i++)
            {
                count[edge[a][i]]--;
                if(!count[edge[a][i]])
                {
                    takennum++;
                    qu.push(edge[a][i]);
                }
            }
        }
        if(takennum==numCourses)
            return true;
        else
            return false;
    }
    

    };


Log in to reply
 

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