我有一个具有N个节点和M个边的图。它是单个组件。
现在，我必须从图形中删除单个节点，删除该节点可能会将图形拆分为1,2个或更多组件。每个删除的节点都需要计数此类组件。 请注意，在任何时间点仅删除一个节点。
我需要在线性时间内对图的所有节点执行此操作。
在线性时间内可以吗？ 通过在每个节点上运行dfs，我可以在O（n ^ 2）中做到这一点。
zcg345 回答：在图中找到总成分
是的，您可以在线性时间内完成。首先，您需要计算图https://en.wikipedia.org/wiki/Biconnected_component的双向连接分量，您可以使用Tarjan算法版本在O（| V | + | E |）时间内完成。然后，对于每个节点，您只需要查看相邻的双向连接组件的数量，就可以在O（| V | + | E |）时间中再次进行计算。
,阅读一些有关“铰接点”的在线资源。 我希望你能得到答案。 https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/