最小化图中的桥数
Minimising Number of Bridges in a Graph
我试图解决一个问题，基本上可以简化为：
给出一组编号为 1 到 N 的 N 个节点和 M 个边，其中 N<10000 和 M<100000,
找到 边 (u,v) 将其添加到图形中时 -- 最小化图中桥的数量。
如果有很多这样的边 - 打印具有最低字典值的那个。
有效解决这个问题的方法是什么？
我觉得这道题很难。以下是我能想到的解决方案的概要：
1) 找出图中所有的桥。
2) 现在假设桥是您想要在图形中唯一的边。你只保留网桥，并在大节点中加入网桥之间的所有节点。
3) 你现在有一棵树。边是桥梁，节点是 "big nodes"，它结合了之前图中的节点。
4) 我们称这个森林图为 T。
5) 连接图 T 中的任意两个节点，创建一个循环。循环中的任何边都不是桥。
6) 第 5 点意味着通过创建可能的最长循环找到解决方案。您可以简单地通过找到两个节点之间距离最长的节点来做到这一点。
7) 您可以在图中找到距离最长的节点。这里是如何讨论的：
A linear-time algorithm for finding the longest distance between two nodes in a free tree?
如果有任何问题需要进一步解释，请告诉我。
我试图解决一个问题，基本上可以简化为：
给出一组编号为 1 到 N 的 N 个节点和 M 个边，其中 N<10000 和 M<100000,
找到 边 (u,v) 将其添加到图形中时 -- 最小化图中桥的数量。
如果有很多这样的边 - 打印具有最低字典值的那个。
有效解决这个问题的方法是什么？
我觉得这道题很难。以下是我能想到的解决方案的概要：
1) 找出图中所有的桥。
2) 现在假设桥是您想要在图形中唯一的边。你只保留网桥，并在大节点中加入网桥之间的所有节点。
3) 你现在有一棵树。边是桥梁，节点是 "big nodes"，它结合了之前图中的节点。
4) 我们称这个森林图为 T。
5) 连接图 T 中的任意两个节点，创建一个循环。循环中的任何边都不是桥。
6) 第 5 点意味着通过创建可能的最长循环找到解决方案。您可以简单地通过找到两个节点之间距离最长的节点来做到这一点。
7) 您可以在图中找到距离最长的节点。这里是如何讨论的： A linear-time algorithm for finding the longest distance between two nodes in a free tree?
如果有任何问题需要进一步解释，请告诉我。