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

• ``````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;
}
};``````

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