c++ - 用于在图中查找内部连接的节点簇的算法，其中没有边缘指向外部

Question

我将我的图表示为邻接列表。我想知道如何找到内部连接但没有边缘点从它们向外的节点集群。有没有我可以使用的众所周知的算法？

例如这是我的图表。

1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4

这里节点 4 和 5 是内部连接的。然而，没有外部优势来自于此。这将是我的答案。同样，节点 1,2,3 即使它们形成一个循环，也不符合标准，因为外部边缘来自节点 3。因此它与在邻接列表中查找循环不同。

可选阅读：（为什么我需要这个）我正在研究排名页面（搜索引擎）算法，像 4 和 5 这样的节点被称为 rank-sink。

Answer 1

您可以使用Kosaraju、Tarjan或Cheriyan-Mehldorn/Gabow算法检测强连通分量。

找到这些组件后，您将每个强连接组件压缩到一个单个节点中（即，您用单个节点表示整个组件）。

在结果图中，您查找没有出边的节点。这些节点代表您感兴趣的组件。