Course Schedule II（C++课程表 II）

淩亂°似流年 2022-09-01 14:50 254阅读 0赞

(1)dfs+stack

  1. class Solution {
  2. private:
  3.     vector<vector<int>> vec;
  4.     vector<int> vis;
  5.     stack<int> s;
  6.     vector<int> res;
  7.     bool tag=true;
  8. public:
  10.     void helper(int x) {
  11.         vis[x]=1;
  12.         for(int i=0;i<vec[x].size();i++) {
  13.             if(vis[vec[x][i]]==0) {
  14.                 helper(vec[x][i]);
  15.                 if(!tag) return;
  16.             } else if(vis[vec[x][i]]==1) {
  17.                 tag=false;
  18.                 return;
  19.             }
  20.         }
  21.         vis[x]=2;
  22.         s.push(x);
  23.         return;
  24.     }
  26.     vector<int> findOrder(int n, vector<vector<int>>& p) {
  27.         vec.resize(n);
  28.         vis.resize(n);
  29.         for(int i=0;i<p.size();i++) {
  30.             vec[p[i][1]].push_back(p[i][0]);
  31.         }
  33.         for(int i=0;i<n&&tag;i++) {
  34.             if(vis[i]==0&&tag) helper(i);
  35.         }
  37.         if(!tag) return {};
  38.         while(!s.empty()) {
  39.             res.push_back(s.top());
  40.             s.pop();
  41.         }
  42.         return res;
  43.     }
  44. };

发表评论

表情：
评论列表 （有 0 条评论，254人围观）

还没有评论，来说两句吧...

相关阅读