Tag
【拓扑排序】【树】
题目来源
题目解读
有一个有 n 个节点的无相无根图，节点编号从 0 到 n-1。有一个表示图中节点间连接关系的数组 edges，长度为 n-1，edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。还有一个数组 coins，coins[i] 为 0 或者 1，表示节点 i 处有一个金币。
你可以选择从任意一个节点出发，你可以收集距离当前节点距离为 2 以内的所有金币，或者移动到当前节点的相邻节点。你需要收集完所有的金币并且最后要返回出发的节点，返回你至少要经过的边数。
比如 示例 1 中，你从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2。你一共经历了边 2——3 和 3——2，所以返回 2，你可以验证这是经历的最少的边数。
示例 1
解题思路
方法一：拓扑排序
我们要经历尽可能少的边来拿完所有的金币，因此一些不必要的边就可以不走，对于那些 “最外侧的” 没有金币的节点，我们不走就好了。而那些 “最外侧” 的节点就是树的叶子节点。
我们可以利用 度数 来判断 “最外侧”，将度数为 1 的节点认定是 “最外侧” 的节点，也就是叶子节点，对于去除了没有金币的叶子节点之后漏出的新的没有金币的叶子节点，同样是 “最外侧” 的节点，我们也要去除掉。从度数为 1 的节点出发，迭代去找度数为 1 的节点进行相应的操作，正是 拓扑排序。
因为，树中一共有 n-1 条边，有 “最外侧” 节点的边不用走，所以在拓扑排序的时候同步更新剩余的边数 left_edges。
经过第一次拓扑排序处理，现在树中的叶子节点都是包含金币的节点了，因为 “你可以收集距离当前节点距离为 2 以内的所有金币”，所以目前的叶子节点及其父节点都不需要走，我们也可以使用拓扑排序的思想砍掉不需要走的边。
我们只需要砍掉 叶子节点——叶节点的父节点 以及新漏出来的 叶子节点——叶节点的父节点 这两类边，因此，可以使用数组来模拟拓扑排序（我们只需要从当前叶子节点向上再找一层）。具体地：
- 首先将叶子节点存入数组
nodes中； - 接着
left_edges - nodes.size()模拟砍掉不必要的边； - 然后遍历
ndoes，枚举数组nodes中的节点x的相邻节点y，如果--degree[y] == 1，则删除x——y之间的边即--left_edges。
最后剩下的 left_edges 就是需要经历的边，因为 “你需要收集完所有的金币并且最后要返回出发的节点”，所以最后的答案为 2 * left_edges。
特别地，如果所有点都要被删除，那么当剩下两个点时，这两个点之间的边我们会删除两次，这会导致剩余边数等于 -1，而此时答案应该是 0。所以最后答案要和 0 取最大值。
以上内容部分参考 拓扑排序（Python/Java/C++/Go/JS/Rust）。
实现代码
class Solution {
public:
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
vector<int> degree(n);
vector<vector<int>> graph(n);
for (auto edge : edges) {
int x = edge[0], y = edge[1];
// 统计节点度数
++ degree[x];
++ degree[y];
// 建边
graph[x].push_back(y);
graph[y].push_back(x);
}
int left_edges = n - 1;
queue<int> que;
for (int i = 0; i < n; ++i) {
if (degree[i] == 1 && coins[i] == 0) {
que.push(i);
}
}
// 模拟删除不含金币的叶子节点以及新漏出的不含金币的叶子节点
while (!que.empty()) {
int x = que.front(); que.pop();
-- left_edges;
for (int y : graph[x]) {
if (--degree[y] == 1 && coins[y] == 0) {
que.push(y);
}
}
}
vector<int> nodes;
for (int i = 0; i < n; ++i) {
if (degree[i] == 1 && coins[i] == 1) {
nodes.push_back(i);
}
}
left_edges -= nodes.size();
// 模拟删除含金币的叶子节点以及新漏出的一层叶子节点
for (int x : nodes) {
for (int y : graph[x]) {
if (--degree[y] == 1)
--left_edges;
}
}
return max(left_edges *2, 0);
}
};
复杂度分析
时间复杂度： O ( n ) O(n) O(n)， n n n 为树中节点个数。
空间复杂度： O ( n ) O(n) O(n)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。
最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。
