如果我们反转一个图（使用Kosaraju的算法），SCC模式会改变吗？
假设我们有一个有向图，它不是一个完整的图，并且有多个SCC。我想知道如果我们将图转置并使用Kosaraju算法，强连通组件的模式是否会发生变化？我所说的“转置图形”是指翻转边的方向。如果我们试图在转置/反转图中而不是原始图中找到SCC，我们找到的SCC会有所不同吗？
我提出这个问题是因为我误解了SCC的算法，并在我的转置/反转图上运行了它。我得到的是与正确答案相同的SCC/它运行Kosaraju的算法。它对所有的图都是普遍正确的吗？
共有1个答案
在Kosaraju的SCC算法中，即使图被反转，其SCC也保持不变，这是一个非常重要的问题。只有SCC之间的链接是反向的。Kosaraju的算法利用这一事实来计算反向图上的DFS，它现在给出了更高的SCC的完成时间值，这些SCC更接近sink SCC。由于Sink SCC对另一个SCC没有输出边，因此在Sink SCC上求DFS可以得到整个连通分量的SCC，并允许将图分解成具有相似性质的子图，在子图上再次应用DFS得到另一个SCC。
-
问题内容： 我试图更改HTML表单，输入类型文件。这是我的代码： HTML，表格ID =表格 .CSS 这两种方法均无效。我确实从某些网站（如Facebook，YouTube，Google或Twitter）看到，它们具有不同的风格。想知道他们是如何做到的。 问题答案： 您不能对输入类型的文件执行任何操作（巨大的黑客攻击除外）。我知道这听起来很可怕，但是Web标准仍然没有提出解决方案。 但是我建议您
-
Kosaraju算法 问题： 用Kosaraju算法求有向图(G)的强连通分支。 解法： Kosaraju算法分为3个步骤： ((1))求出图(G)的逆图(G’)； ((2))求出逆图(G’)的拓扑排序(T)； ((3))按照逆图(G’)拓扑排序(T)的顺序，对原图(G)中每个节点进行DFS，得到的森林即为所求的强连通分支。注意每个节点只能属于一个强连通分支，因此当一个节点被DFS遍历到后，需要将
-
最近在一次采访中，我解释了我所研究的一个框架。我说过，我们通过使用模板方法设计模式提供扩展性，创建了一个控制反转。我说这是一个控制反转的例子，我们的框架调用框架用户实现的方法，采访者说模板方法设计模式不是IOC的例子。我想知道我对国际奥委会的理解是否有误？
-
我使用反应钩。如果道具被改变了，有什么方法可以获得初始值？我想避免反模式效应。 场景1：在构建DOM之前。 据我所知，就这些目的而言，这是一份备忘录。如果有其他选项，您可以选择显示它们。 情景2：在DOM之后 在这个变体中，useLayoutEffect，useEffect。如果有其他选项，您可以选择显示它们。 我认为使用所有这些挂钩不是一个好的做法。但我看不到其他解决办法。也许还有第三种不使用挂
-
问题内容： 我在html表中有图像列表，并且需要在每个图像上重叠一个小图标。我们如何使用z索引和定位来做到这一点？ 问题答案：
-
在上一节中的计算器是以解释的方式执行的，现在我们想要把它转换成以编译的方式执行。编译执行和解释执行相比，需要依赖于特定的目标机器。在这里我们假设有一台这样的机器，它用堆栈进行运算，支持如下表所示的几种指令： 指令 说明 运算元数目 用途 LDV Load Variable 1 变量入栈 LDC Load Constant 1 常量入栈 STR Store Value 1 栈顶一个元素存入指定变量