Share my C++ solution using BFS,easy to understand


  • 1
    V
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> edges(numCourses, vector<int>(0));
            vector<int> indegree(numCourses ,0);//the indegree of vertex
            queue<int> q;//stroe the vertex that the indegree is zero
            
            vector<pair<int, int>>::iterator iter;
            vector<pair<int, int>>::iterator end = prerequisites.end();
            int vertex = 0;
            int edge_cnt = prerequisites.size();
            
            for (iter = prerequisites.begin(); iter != end; iter++)
            {
                edges[iter->first].push_back(iter->second);
                indegree[iter->second]++;
            }
            
            for (int i = 0; i < numCourses; i++)
            {
                if (indegree[i] == 0)
                    q.push(i);
            }
            
            while (!q.empty())
            {
                if (edge_cnt == 0)
                    return true;
    
                vertex = q.front();
                q.pop();
                
                int len = edges[vertex].size();
                for (int i = 0; i < len; i++)
                {
                    int temp = edges[vertex][i];
                    indegree[temp]--;
                    edge_cnt--;
                    if (indegree[temp] == 0)
                        q.push(temp);
                }
            }
            
            return false;
        }
    };

Log in to reply
 

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