c++ - 路径上的最大节点数是多少？

Question

我遇到了以下问题:

有很多节点，其中几个已经连接，但不是全部。我们必须添加连接，以便每个节点都与任何其他节点连接(不需要直接连接)。我们不想更改任何现有连接。节点必须连接最少的线路(当前连接已遵循此规则)。此外，从一个节点到另一个节点的路径必须经过最少数量的其他节点。当一切都以最佳方式连接时，我们想知道任何路径上的最大节点数。

输入:
以下数据由用户输入给出:
• 你得到两个整数:节点数 1 ≤ p ≤ 1.000.000 和数量 0 ≤ l ≤ p − 1 个现有连接。
• 然后 l 行每两个整数 a 和 b 介于 0 和 p 之间− 1(含)，表示连接的端点。

输出:
输出应该是一个整数，表示任何路径上的最大节点数。(因此没有开始和结束点)

例如，当我们有输入 p = 6、l = 4 和连接 2-0、1-0、5-3 和 4-3输出应该是 2。

我已经用 C++ 编写了一个程序，它执行以下操作:

int main(){

    int p, l;

    cin >> p >> l;

    for (int i = 0; i < l; i++){

        int a, b;

        cin >> a >> b;

        // store the connection a,b somehow

    }

    // solve the problem

    cout << answer << endl;

}

我想将连接存储在一个 p - 1 乘以 p - 1 的数组中，如果该行存在则为 1，否则为 0。此外，我需要一些东西来决定如何以最佳方式建立连接并计算每条路径上的最大节点数。我只被允许使用 C++ 的标准库。

有人可以帮我解决这个问题吗？提前致谢!

Answer 1

这听起来像是基本的算法作业......

给定您的现有图，找到最大路径。除非您只有两个节点，否则这就是您的答案。

将所有新节点连接到不是最大路径的叶节点的任何节点。

(连接节点的线称为“边”。)

如果我误解了您的问题，请告诉我。

编辑这是一个简单的图表。最大路径是 (a,b,c) [与 (c,b,a) 相同——我们总是对两片叶子进行排序，以便最小的先出现]。

(a)--(b)--(c)

我可以通过选择任何 叶 节点(恰好有 1 个边的节点)并找到通往另一个叶节点的路径来找到它。最远的叶节点将是从该节点的最长/最大路径。

从刚刚找到的叶子节点开始再做一次，你将得到整个图的最长/最大路径。

让我们检查一下它如何使用新图:

(a)--(b)--(c)--(d)--(e)--(f)
           |
          (s)

我将从节点 (s) 开始。如果我找到最长的路径，我会找到节点 (f)。节点 (f) 必须是图中最长路径上的端点之一。 (我会留给你思考原因。)

现在，我再次从节点 (f) 开始。从 (f) 到 (a) 的最长路径。我现在拥有图中最长的路径:(a,b,c,d,e,f)。

这是另一个图表:

(a)--(b)--(c)
      |
     (d)

有许多最长的路径可供选择。 (a,b,c)、(a,b,d) 和 (c,b,d)。重要的是它们都存在并且具有相同的长度。

现在，我应该将一个新 节点 (e) 连接到哪个节点，这样我就不会更改最长路径？简单:

     (e)
      |
(a)--(b)--(c)
      |
     (d)

您可以通过仅将新节点附加到不是叶节点的节点来保证这一点。

至于您关于如何表示图形的问题，您的想法可以正常工作，但请记住，您有 p 个节点，而不是 p-1。因此，例如，我可以将我的 3 节点图表示为:

       from
      a  b  c 
   a  0  1  0
to b  1  0  1
   c  0  1  0

注意列:a 只通向另一个节点。同样，c 只通向另一个节点。但是，b 的列显示 b 通向 两个 个其他节点(不止​​一个)。

因此，a和c是叶子； b 不是。

如果我添加一个新节点，我只想将它连接到已经有多个节点的节点:

   a  b  c  d            a  b  c  d
a  0  1  0  0         a  0  1  0  0
b  1  0  1  0   -->   b  1  0  1  1
c  0  1  0  0         c  0  1  0  0
d  0  0  0  0         d  0  1  0  0

希望这对您有所帮助。