【拓扑排序】【 图论】1203. 项目管理

class CTopSort
{
public: 
  void Init(const vector<vector<int>>& vNeiBo)
  {
    m_c = vNeiBo.size();
    m_vBackNeiBo.resize(m_c);
    vector<int> vOutDeg(m_c);
    for (int cur = 0; cur < m_c; cur++)
    {
      vOutDeg[cur] = vNeiBo[cur].size();  
      for (const auto& next : vNeiBo[cur])
      {
        m_vBackNeiBo[next].emplace_back(cur);
      }
    }
    queue<int> que;
    for (int i = 0; i < m_c; i++)
    {
      if (0 == vOutDeg[i])
      {
        que.emplace(i);
        m_vLeaf.emplace_back(i);
        OnDo(-1, i);
      }
    }
    while (que.size())
    {
      const int cur = que.front();
      que.pop();
      for (const auto& next : m_vBackNeiBo[cur])
      {
        vOutDeg[next]--;
        if (0 == vOutDeg[next])
        {
          que.emplace(next);
          OnDo(cur, next);
        }
      }
    };
  }
  int m_c;
  vector<int> m_vLeaf;
protected:
  virtual void OnDo(int pre, int cur) = 0;
  vector<vector<int>> m_vBackNeiBo;
};
class CMyTopSort : public CTopSort
{
public:
  CMyTopSort(const vector<int>& vNodeToGroup,int iGroupCount):m_vNodeToGroup(vNodeToGroup)
  {
    m_vNodeOfGroup.resize(iGroupCount);
  }
  vector<vector<int>> m_vNodeOfGroup;
  vector<int> m_vGroupNo;
protected:
  virtual void OnDo(int pre, int cur) override
  {
    if (cur < m_vNodeToGroup.size())
    {
      const int iGroup = m_vNodeToGroup[cur];
      m_vNodeOfGroup[iGroup].emplace_back(cur);
      m_vGroupNo.emplace_back(iGroup);
    }   
  }
  const vector<int>& m_vNodeToGroup;
};
class Solution {
public:
  vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
    int iMaxGroup = *std::max_element(group.begin(), group.end());
    for (auto& tmp : group)
    {
      if (-1 == tmp)
      {
        tmp = ++iMaxGroup;
      }
    }
    vector<vector<int>> vNodeOfGroup(iMaxGroup + 1);
    for (int i = 0; i < group.size(); i++)
    {
      vNodeOfGroup[group[i]].emplace_back(i);
    }
    vector<vector<int>> vNeiBo((1 + iMaxGroup)*2+n );
    for (int i = 0; i < vNodeOfGroup.size(); i++)
    {
      for (const auto& tmp : vNodeOfGroup[i])
      {
        vNeiBo[tmp].emplace_back(n + 2 * i);//组内所有节点都依赖组前节点
        vNeiBo[n + 2 * i + 1].emplace_back(tmp);//组后节点依赖所有组内节点
      }
    } 
    for (int i = 0; i < beforeItems.size(); i++)
    {
      for (const auto& bef : beforeItems[i])
      {
        if (group[i] == group[bef]) {
          vNeiBo[i].emplace_back(bef);
        } 
        else {
          vNeiBo[n + 2 * group[i]].emplace_back(n + 2 * group[bef] + 1);
        }
      }
    }
    for (auto& v : vNeiBo)
    {//删除重复节点
      unordered_set<int> tmp(v.begin(), v.end());
      vector<int>(tmp.begin(), tmp.end()).swap(v);
    }   
    CMyTopSort top(group,iMaxGroup+1);
    top.Init(vNeiBo);   
    vector<int> vRet;
    for (const auto& tmp : top.m_vGroupNo)
    {
      auto& v = top.m_vNodeOfGroup[tmp];
      vRet.insert(vRet.end(), v.begin(), v.end());
      v.clear();
    }
    return (vRet.size() == group.size()) ? vRet : vector<int>{};
  }
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  int n,  m;
  vector<int> group;
  vector<vector<int>> beforeItems;
  {
    Solution sln;
    n = 8, m = 2, group = { -1,-1,1,0,0,1,0,-1 }, beforeItems = { {},{6},{5},{6},{3},{},{4},{} };
    auto res = sln.sortItems(n, m, group, beforeItems);
    Assert({ }, res);
  }
  {
    Solution sln;
    n = 8, m = 2, group = { -1,-1,1,0,0,1,0,-1 }, beforeItems = { {},{6},{5},{6},{3,6},{},{},{} };
    auto res = sln.sortItems(n, m, group, beforeItems);
  //  Assert({ 6,3,4,1,5,2,0,7 }, res);
  } 
}

return vRet;
}
vector<int> Order(vector<set<int>>& vBefore, vector<set<int>>& vAfter)
{ 
  vector<int> vOrders;
  for (int j = 0; j < vBefore.size(); j++)
  {
    if (vBefore[j].size() == 0)
    {
      vOrders.emplace_back(j);
    }
  }
  int hasDo = 0;
  while (hasDo < vOrders.size())
  {
    const auto cur = vOrders[hasDo];
    hasDo++;
    for (auto& after : vAfter[cur])
    {
      vBefore[after].erase(cur);
      if (vBefore[after].empty())
      {
        vOrders.emplace_back(after);
      }
    }
    vAfter[cur].clear();
  }
  return vOrders;
}
vector<vector<int>> m_vGroupItems;