|
|
1
1
首先,将图形分割成连接的组件,这可以通过执行深度优先或广度优先搜索在O(n)时间和内存中完成。 如果任何节点未连接到另一个节点,则解决方案是不可能的。 从每个DFS/BFS树的叶子(即仅连接到另一个节点的节点)开始,将每个连接的组件拆分为相邻节点的成对(或三元组)。每一对(或三元组)都应该进入下一个存储桶,其中的节点数最少。
从左叶删除2个节点。
从右叶删除2个节点。
这将在剩余子图中创建一个新的1阶顶点,以便删除该顶点及其相邻顶点:
只剩下3个顶点,如果它能放进一个桶里,那么就把它放进桶里——否则就把一对从物品数量最少的桶里移到物品数量次之的桶里,然后把三元组加进去。
唯一的问题将是当你得到星形连接组件
|
|
|
feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点 1 年前 |
|
|
Alisa Petrova · 在有向图中更改一对顶点以创建循环 1 年前 |
|
|
b39b332d · 使用C++标准库实现高效间隔存储 2 年前 |
|
ABGR · 二叉树的直径——当最长路径不通过根时的失败案例 2 年前 |
|
|
EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字 2 年前 |