是否有解决以下决策问题的算法：
给定一个由其转换矩阵定义的强连接加权有向图G，是否存在没有负周期的G的强连接生成子图？
G的强连接子图是G的强连接子图，与G共享相同的顶点。您可以在paper中查找强连接的跨子图的定义。在本文中，他们为最小强连通子图问题提供了一个近似值。
天真的方法是使用Ford-Bellman或Floyd-Warshall算法找到图形的负循环，从该循环中删除边，并在图形仍保持牢固连接的情况下重复进行。但是这种天真的方法的时间复杂度很差，因为我们可能会运行福特贝尔曼算法并多次检查强连通性-而且我无法证明该算法在所有情况下都是正确的。
我希望在这里找到专家，他们可以告诉我这个决策问题是否可以在多项式时间内解决，以及采用哪种算法可以解决。提前非常感谢。
这里是一个幼稚的解决方案，它有合理的机会找到在多项式时间内没有负循环的强连通生成子图。但强调不能保证找到一个。
将所有权重设为负数。现在，使用福特·贝尔曼或弗洛伊德·沃歇尔来寻找一个负周期。这实际上是原始图中的一个[[positive循环。
现在我们在循环中选择一个顶点，然后将其他顶点收缩到该顶点。连接到/来自已移除顶点的边被表示沿该边并围绕循环行进至我们保留的边的边替换。如果在两个顶点之间有多个边，则只保留最佳的一个。在新的较小的图形上重复练习。
此算法在保证的多项式时间内运行（每个迭代均在多项式时间内运行，并删除至少一个顶点）。如果它设法将图形缩小到一个点，那么您只需向后走，发现实际上找到了一个没有负周期的强连通生成图。
但是，如果这样做失败，则不能保证没有一个。您只是没有找到它。
（（我怀疑有保证的算法将是NP完整的。）