SHARE
TWEET

Untitled

a guest Jul 18th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  4.         unordered_map<int, int> degree;
  5.         unordered_map<int, unordered_set<int>> graph;
  6.        
  7.         for (int i = 0; i < numCourses; ++i) {
  8.             degree[i] = 0;
  9.         }
  10.        
  11.         for (const auto& course: prerequisites) {
  12.             degree[course[0]]++;
  13.             graph[course[1]].insert(course[0]);
  14.         }
  15.        
  16.         queue<int> q;
  17.         for (int i = 0; i < numCourses; ++i) {
  18.             if (degree[i] == 0) {
  19.                
  20.                 q.push(i);
  21.             }
  22.         }
  23.        
  24.         while (!q.empty()) {
  25.             int id = q.front(); q.pop();
  26.             numCourses--;
  27.            
  28.             for (const auto& child : graph[id]) {
  29.                 degree[child]--;
  30.                 if (degree[child] == 0) {
  31.                     q.push(child);
  32.                 }
  33.             }
  34.         }
  35.        
  36.         return numCourses == 0;
  37.     }
  38. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top