0

第一：我承认这是编程竞赛的一部分（没有什么可以赢或什么的）

在阅读了问题并尝试了以下算法后，我得出了以下结论。

给定n顶点的无向连通图，

count = 0
For i=1 to n:
  remove(ith vertex)
  check for connectivity of graph with remaining vertices
  if connected 
    then increment count
  attach the removed vertex back
print count

我通过两种方式实现了这一点：(1) DFS (2) Disjoint-Set Union 但是没有一种算法足够有效地获得 AC。是否有更好的方法来做到这一点？我不需要详细的解释，几句话就可以了，休息我会弄清楚或死去尝试：p。谢谢你！

4

2 回答 2

5

一个顶点的删除使图形断开连接称为关节点。图中的所有关节点都可以在线性时间内找到。

于 2013-04-24T16:03:19.887 回答
1

根据您的输入图，有几个选项，每个选项都有自己的优势。我个人不会模拟每个节点的故障，然后检查整个图中的连通性，这需要太多时间。

更聪明的方法可能是构建生成树。这棵树上的每一片叶子都可以在不断开图的其余部分的情况下被移除，因为树的其余部分仍然连接其他所有部分。建造一棵树可以让您跳过单独检查的叶子。您甚至可以构建更多的树来尝试让其他一些节点（非叶子）成为叶子（然后可以跳过）。来自多个节点的 BFS 可以帮助您入门。

此外，当您模拟移除 1 个节点时，您只需检查其邻居是否仍然相互连接。如果邻居是连通的，那么图的其余部分也是连通的。如果图很密集，这应该会限制每个节点的工作量。

于 2013-04-08T17:47:11.533 回答