【图论】【树】【拓扑排序】2603. 收集树中金币-阿里云开发者社区

本文涉及知识点

图论树拓扑排序

LeetCode 2603. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者

移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]

输出：2

解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]

输出：2

解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

提示：

n == coins.length

1 <= n <= 3 * 10⁴

0 <= coins[i] <= 1

edges.length == n - 1

edges[i].length == 2

0 <= ai, bi < n

ai != bi

edges 表示一棵合法的树。

拓扑排序

利用拓扑排序不断删除没有金币的叶子节点，不影响答案。

如果根节点没有金币且只有一个孩子，删除。它的孩子成为新的根。简便方式是直接选择有金币的节点为根。其实，拓扑排序后，不会存在这样的根。

一个子树cur有若干金币，且叶子节点的最早公共祖先是cur。则收集所有金币只需要：移动到叶子祖父节点，再回来。

如果cur是整个树的根，则收集结束。等于：除非叶子节点、非叶子节点父亲外所有节点× \times×*2。

如果不是根，cur 需要通过根收集金币，所以cur → \rightarrow→ root 路径上的边，也要来回一次。

对于任意cur，cur → \rightarrow→ parent 和parent → \rightarrow→ cur都只需要执行一次。

因为一次就可以收集所有金币。

题解

拓扑排序删除非金币节点后。

错误解法

DFS，返回cur距离叶子最远距离，如果>=2 ，则m_iRet+=2。注意：根节点不算，它没有父节点。DFS的时候排除已经被拓扑排序删除的节点。叶子节点到叶子节点的距离是0。果没有金币，直接返回0。错误原因：不同的根节点，结果不一样。

正确解法

删除叶子节点（无论是否有金币）两次。如果余下的节点为0，则返回0，否则返回( 剩余节点数-1)× \times× 2

代码

核心代码

class CTopSort
{
public: 
  template <class T = vector<int> >
  void Init(const vector<T>& vNeiBo,bool bDirect = true )
  {
    const int iDelOutDeg = bDirect ? 0 : 1;
    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);
      }
    }
    vector<bool> m_vHasDo(m_c);
    queue<int> que;
    for (int i = 0; i < m_c; i++)
    {
      if ( vOutDeg[i] <= iDelOutDeg)
      {
        m_vHasDo[i] = true;
        if (OnDo(i)) {
          que.emplace(i);
        }
      }
    }
    while (que.size())
    {
      const int cur = que.front();
      que.pop();
      for (const auto& next : m_vBackNeiBo[cur])
      {
        if (m_vHasDo[next] )
        {
          continue;
        }       
        vOutDeg[next]--;
        if (vOutDeg[next] <= iDelOutDeg )
        {
          m_vHasDo[next] = true;
          if (OnDo(next)) {
            que.emplace(next);
          }
        }
      }
    };
  }
  int m_c;
protected:
  virtual bool OnDo( int cur) = 0;
  vector<vector<int>> m_vBackNeiBo; 
  
};

测试用例

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()
{
  vector<int> coins;
  vector<vector<int>> edges;
  {
    Solution sln;
    coins = { 1,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0 }, edges = { {0,1},{0,2},{1,3},{2,4},{2,5},{3,6},{3,7},{4,8},{7,9},{8,10},{10,11},{11,12},{7,13},{8,14},{9,15},{11,16},{13,17} };
    auto res = sln.collectTheCoins(coins, edges);
    Assert(10, res);
  }
  {
    Solution sln;
    coins = { 1,0,0,1,1,0,0,0,0,1,0,0 }, edges = { {0,1},{1,2},{1,3},{2,4},{4,5},{5,6},{5,7},{4,8},{7,9},{7,10},{10,11} };
    auto res = sln.collectTheCoins(coins, edges);
    Assert(4, res);
  }
  {
    Solution sln;
    coins = { 1,0,0,0,0,1 }, edges = { {0,1},{1,2},{2,3},{3,4},{4,5} };
    auto res = sln.collectTheCoins(coins, edges);
    Assert(2, res);
  }
  {
    Solution sln;
    coins = { 0,0,0,1,1,0,0,1 }, edges = { {0,1},{0,2},{1,3},{1,4},{2,5},{5,6},{5,7} };
    auto res = sln.collectTheCoins(coins, edges);
    Assert(2, res);
  } 
}

2023年4月

class Solution {
public:
int collectTheCoins(vector& coins, vector<vector>& edges) {
m_c = coins.size();
vector vDeg(m_c);
vector<vector> vNeiB(m_c);
for (const auto& v : edges)
{
vNeiB[v[0]].emplace_back(v[1]);
vNeiB[v[1]].emplace_back(v[0]);
vDeg[v[0]]++;
vDeg[v[1]]++;
}
std::queue que;
for (int i = 0; i < m_c; i++)
{
if ((0 == coins[i]) && (1 == vDeg[i]))
{
que.emplace(i);
}
}
//根据Top排序，依次删除没有金币的节点，自己和子节点没有金币的节点， 自己和子孙节点没金币的节点…
while (que.size())
{
int iCur = que.front();
que.pop();
for (const auto& next : vNeiB[iCur])
{
vDeg[next]–;
if ((0 == coins[next]) && (1 == vDeg[next]))
{
que.emplace(next);
}
}
vNeiB[iCur].clear();
}
//通过top排序生成平衡树，Dis为0，表示页节点；1表示离最近的叶节点为1
//访问所有完所有Dis为2的节点，可以收集所有金币
//每个叶子只有一个父节点，自然只有一个祖父节点。必须访问所有Dis为2的节点，否则它子孙的金币无法收集
//
//叶节点入队
vector vDis(m_c, 0);
for (int i = 0; i < m_c; i++)
{
if (1 == vDeg[i])
{
que.emplace(i);
}
}
if (que.size() <=1)
{
return 0;
}
while (que.size())
{
const int iCur = que.front();
que.pop();
for (const auto& next : vNeiB[iCur])
{
vDeg[next]–;
if (1 == vDeg[next])
{
que.emplace(next);
vDis[next] = vDis[iCur] + 1;
}
}
vNeiB[iCur].clear();
}
//
int iRet = -2;
for (int i = 0; i < m_c; i++)
{
if (vDis[i] >= 2)
{
iRet += 2;
}
}
return max(0,iRet);
}
int m_c;
};

2023年8月

class Solution {
public:
int collectTheCoins(vector& coins, vector<vector>& edges) {
m_c = coins.size();

CNeiBo2 neiBo(m_c, edges, false);
  vector<int> vDeg(m_c);
  for (const auto& v : edges)
  {
    vDeg[v[0]]++;
    vDeg[v[1]]++;
  }
  std::queue<int> que,queCoins;//非金币叶子 金币叶子
  vector<int> vDel(m_c);
  for (int i = 0; i < m_c; i++)
  {
    if (1 == vDeg[i])
    {
      if (0 == coins[i])
      {
        que.emplace(i);         
      }
      else
      {
        queCoins.emplace(i);
      }
    }
  }
  while (que.size())
  {
    const int cur = que.front();
    que.pop();
    vDel[cur] = true;
    for (const auto& next : neiBo.m_vNeiB[cur])
    {
      vDeg[next]--;
      if (1 == vDeg[next])
      {
        if (0 == coins[next])
        {
          que.emplace(next);
        }
        else
        {
          queCoins.emplace(next);
        }
      }
    }
  }
  queue<int> queParent;
  while (queCoins.size())
  {
    const int cur = queCoins.front();
    queCoins.pop();
    vDel[cur] = true;
    for (const auto& next : neiBo.m_vNeiB[cur])
    {
      vDeg[next]--;
      if (1 == vDeg[next])
      {
        queParent.emplace(next);
        vDel[next] = true;
      }
    }
  }
  int iRet = 0;
  for (const auto& v : edges)
  {
    if (vDel[v[0]] || vDel[v[1]])
    {
      continue;
    }
    iRet += 2;
  }
  return iRet;
}
int m_c;

};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【图论】【树】【拓扑排序】2603. 收集树中金币

本文涉及知识点

LeetCode 2603. 收集树中金币

拓扑排序

题解

错误解法

正确解法

代码

核心代码

测试用例

2023年4月

2023年8月

扩展阅读

视频课程

相关

测试环境

热门文章

最新文章

相关课程

相关电子书

【图论】【树】 【拓扑排序】2603. 收集树中金币

本文涉及知识点

LeetCode 2603. 收集树中金币

拓扑排序

题解

错误解法

正确解法

代码

核心代码

测试用例

2023年4月

2023年8月

扩展阅读

视频课程

相关

测试环境

热门文章

最新文章

相关课程

相关电子书

【图论】【树】【拓扑排序】2603. 收集树中金币