algorithm - 单边加法可最大程度地减少图中的桥数

Question

我们给了一个图g，它有n个顶点，m个边，n<=10^4，m<=10^5。现在，您必须向图中恰好添加一条边（u，v），这样桥的总数就最小化了。G可以有多个边，但没有自循环另一方面，新生成的图在添加边g'之后可能同时具有自循环和多个边。如果许多这样的（u，v）与u 一个简单的想法是按顺序尝试所有边，然后使用桥查找算法来查找桥的数量。这需要时间O（V^2*E），所以它显然是无用的如何在运行时做得更好？
编辑：根据j_random_hacker的建议，我添加了关于上述问题来源的以下详细信息。这是一个名为计算机网络的问题（特别是问题3），来自印度IOI训练营14年的实践测试（测试3）。这是一个现场离线测试，所以我无法通过提供链接来证明它不是来自当前的比赛但我有一份问题陈述的pdf文件。

Answer 1

这不是一个完整的答案，而是一些引导你走向它的想法：
为了避免在尝试每个可能的边之后运行桥查找算法，有必要问：通过添加单个边（u，v）可以在多大程度上更改图g中的桥数？
如果u和v还没有通过g中的任何路径连接起来，那么（u，v）本身肯定会成为一座桥。那“桥牌”呢新娘？）所有其他顶点对中它变了吗？（最重要的是：有什么优势可以从桥变成非桥吗如果你能证明这是不可能发生的，那么你可以立即放弃所有这样的顶点对（u，v），因为它们只会使情况变得更糟
如果U和V已经连接在G中，则有两种可能：
连接它们的每个路径p都有一些边（x，y）（注意x和y不一定与u和v不同）。然后（x，y）是g中的一个桥，加上（u，v）将导致（x，y）不再是桥，因为这样就有可能从x到y“长途跋涉”，从x回到u，通过新边（u，v）到v，再回到y（这假设x在p上比y更接近u，但很明显，如果y更接近，这个论点仍然有效：只需交换u和v）可能有多个这样的桥（x，y）：在这种情况下，在添加（u，v）之后，所有的桥都将变成非桥。
至少有两条边不相交的路径p和q已经连接u和v。显然p或q上没有边（x，y）可以是桥，因为如果p上的（x，y）被删除了，仍然可以通过q从x到y“漫长的路”。问题是：所有其他顶点对的桥度如何？您应该能够证明这个属性没有改变，这意味着添加边（u，v）将使桥的总数保持不变，因此可以忽略为无用的移动（除非根本没有桥可以开始）。
我们看到上面的2.1是添加边（u，v）可能有用的唯一情况。而且，似乎我们在一条路径中找到的桥越多，我们就越能通过选择连接该路径的端点来中和它们。
因此，“在g中找到包含最多桥的路径”似乎是正确的标准。但首先我们需要扪心自问：路径p中的桥数是否精确地计算了从p的开始到结束添加一个边而消除的桥数？（我们知道添加这样一个边必须至少消除这些桥，但也许其他一些桥也会作为“副作用”被消除——如果是这样，那么我们需要以某种方式计算它们，以确保添加的边可以消除总体上最多的桥。）
令人高兴的是，答案是没有其他桥梁被消除。这次我自己来做证明。
假设从u到v有一条路径p，相反地假设增加边（u，v）将消除不在p上的桥（x，y）。那么，必须是从x到y的唯一路径是单边（x，y），并且增加（u，v）将从x创建第二条路径q，通过沿任意方向的边（u，v）。到避免边的y（x，y）。但是对于任何这样的q，我们可以用路径p代替q中的边（u，v），从我们最初的假设中，路径p避免了（x，y），并且仍然得到一条从x到y的路径q'来避免边（x，y）--这意味着（x，y）必须已经由两条边不相交的路径（即单边（x，y）和q'）连接，所以它不可能是桥首先。因为这是一个矛盾，因此不存在这样的“副作用”桥（x，y）。
所以“在g中找到包含最多桥的路径，并在其端点之间添加一条边”肯定给出了正确的答案——但仍然存在一个问题：这听起来很像最长路径问题，对于一般的图来说，这是np难的问题，因此解决起来很慢。
然而，有一条出路（必须有：你已经有一个O（V^2*E）算法，所以你的问题不可能是NP难的：-）把你的输入图G中的双连通分量看作是另一个图G'中的顶点这些顶点（in g'）之间的边与in g对应什么？它们有什么特殊的结构吗？最后（大）提示：什么是关键路径？