Leetcode-5200 Sort Items by Groups Respecting Dependencies(项目管理)

我不是女神ヾ 2023-06-01 08:56 10阅读 0赞

1 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      2 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      3 #define INF 0x3f3f3f3f
      4 #define MOD 1000000007
      5 #define pb push_back
      6 #define maxn 100003
      7 
      8 class Solution
      9 {
     10     public:
     11         int N,M,K;
     12         vector<int> Gp[60003];//每个组有哪些项目 
     13         
     14         int ing[60003];//以组为单位的入度 
     15         vector<int> GG[60003];//以组为单位的存图
     16         
     17         int in[60003];//以组内项目为单位的入度
     18         vector<int> G[60003];//以组内项目为单位的存图 
     19         
     20         int Group[60003];//G[i]表示项目i在G[i]组内 
     21         vector<int> gans;//组的顺序
     22         vector<int> ans;//最终的答案 
     23 
     24         bool topo1()
     25         {
     26             int cnt = 0;
     27             queue<int> q;
     28             int count = 0;
     29             _for(i,0,M+K) 
     30                 if(!ing[i])
     31                     q.push(i);
     32             while(!q.empty())
     33             {
     34                 int begin = q.front();
     35                 q.pop();
     36                 gans.pb(begin);
     37                 cnt ++;
     38                 for (int i = 0; i < GG[begin].size(); i ++)
     39                     if (--ing[GG[begin][i]]==0)
     40                         q.push(GG[begin][i]);
     41             }
     42             if(cnt == M+K)
     43                 return true;
     44             else
     45                 return false;
     46         }
     47         
     48         bool topo2(int cur)
     49         {
     50             int cnt = 0;
     51             queue<int> q;
     52             _for(i,0,Gp[cur].size()) 
     53                 if(!in[Gp[cur][i]])
     54                     q.push(Gp[cur][i]);
     55             while(!q.empty())
     56             {
     57                 int begin = q.front() ;
     58                 q.pop();
     59                 ans.pb(begin);
     60                 cnt ++;
     61                 for (int i = 0; i < G[begin].size(); i ++)
     62                     if (--in[G[begin][i]]==0)
     63                         q.push(G[begin][i]) ;
     64             }
     65             if(cnt == Gp[cur].size())
     66                 return true;
     67             else
     68                 return false;
     69         }
     70         
     71         vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems)
     72         {
     73             N = n,M = m;
     74             _for(i,0,n)
     75                 if(group[i]!=-1)
     76                 { 
     77                     Gp[group[i]].pb(i);
     78                     Group[i] = group[i]; 
     79                 }
     80                 else
     81                 {
     82                     Group[i] = M + K;
     83                     K ++; 
     84                     Gp[Group[i]].pb(i);
     85                 }
     86             
     87             _for(i,0,n)
     88                 _for(j,0,beforeItems[i].size())
     89                     if(Group[beforeItems[i][j]] != Group[i])
     90                     {
     91                         GG[Group[beforeItems[i][j]]].pb(Group[i]);
     92                         ing[Group[i]] ++;
     93                     }
     94                     else
     95                         if(Group[i] <= M+K)
     96                         {
     97                             G[beforeItems[i][j]].pb(i);
     98                             in[i] ++;
     99                         }
    100             
    101             vector<int> ti;
    102             if(!topo1())
    103                 return ti;
    104             _for(i,0,M+K)
    105                 if(!topo2(gans[i]))
    106                     return ti;
    107             return ans;
    108         }
    109 };

其实在建图的时候还可以用set维护一下，防止重边加入，不过.....数据好像挺弱就不需要了

转载于:https://www.cnblogs.com/Asurudo/p/11571791.html