keverman

Topsort

Feb 8th, 2020 (edited)
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. vector<int> topsort(vector<vector<int>>&edges)
  2. {
  3.     vector<int> in_degree(edges.size(), 0), tsort;
  4.     queue<int> Q;
  5.  
  6.     for (int u = 0; u < edges.size(); u++)
  7.         for (int v : edges[u])
  8.             in_degree[v]++;
  9.  
  10.     for (int u = 0; u < edges.size(); u++)
  11.         if (in_degree[u] == 0)
  12.             Q.push(u);
  13.  
  14.     while (!Q.empty())
  15.     {
  16.         int u = Q.front(); Q.pop();
  17.         tsort.push_back(u);
  18.  
  19.         for (int v : edges[u])
  20.             if (--in_degree[edges.size()] == 0)
  21.                 Q.push(v);
  22.     }
  23.  
  24.     return tsort;
  25. }
Add Comment
Please, Sign In to add comment