问题标签 [kosaraju-algorithm]

Required regex pettern like

1. allow only letters with min 1 dot and maximum 3 dots.
2. allow optional as '-' special character.

Ex: raj.gopal-reddy or raj.reddy.gopal

TLE 代码在 2.1 秒内完成。我也通过参考传递了很多东西，但它仍然抛出一个 TLE。为什么这段代码需要这么多时间？

这是hackerearth的问题：

https://www.hackerearth.com/problem/algorithm/falling-dominos-49b1ed46/

多米诺骨牌很有趣。孩子们喜欢把瓷砖竖着排成一长队。当一张多米诺骨牌倒下时，它会撞倒下一张，然后再撞倒另一张，一直向下。然而，有时一张多米诺骨牌无法击倒下一张。在这种情况下，我们必须用手将其击倒以使多米诺骨牌再次倒下。你的任务是根据一些多米诺骨牌的布局确定必须用手击倒的骨牌的最小数量才能使所有骨牌倒下。

输入

输入的第一行包含一个整数，指定要遵循的测试用例的数量。每个测试用例都以包含两个整数的行开始，每个整数不大于 100 000。第一个整数 n 是多米诺骨牌的数量，第二个整数 m 是测试用例中要遵循的行数。多米诺牌从 1 到 n 编号。以下每一行都包含两个整数 x 和 y，表示如果 domino 编号 x 下降，它将导致 domino 编号 y 也下降。

输出

对于每个测试用例，输出一行，其中包含一个整数，即为使所有多米诺骨牌倒下而必须用手打倒的最少骨牌数量。

样品输入 1 3 2 1 2 2 3 样品输出 1

代码在 2.1 完成

高效代码在 0.7 秒内完成。

对于给定的有向图G，我需要使用 Kosaraju 算法计算其强连通分量 (SCC)。据我了解，算法的步骤如下：

1. 让G rev = G将所有弧反转
2. 在G rev 上运行DFS（深度优先搜索）以计算节点的完成时间
3. 在G上运行DFS以发现 SCC

我已经设法找到所有节点的正确完成时间。我部分理解我应该将完成时间分配给其各自的节点值，反转图G rev，然后在反转图（现在G ）上再次运行 DFS，完成时间作为节点值处理节点，按完成时间的递减顺序. 我的理解正确吗？如果是这样，我该如何编码？

这是我到目前为止的地方：

fin_times应该是{3: 1, 5: 2, 2: 3, 8: 4, 6: 5, 9: 6, 1: 7, 4: 8, 7: 9}，并且如前所述，它是正确的。我现在与我有什么关系fin_times？

此外，我迭代而不是递归地执行它的原因是分配的输入文件太大并且程序将达到递归限制。

编辑：在回答问题后，我意识到这个问题不符合课程的荣誉准则。我编辑了问题以排除可能会泄露分配解决方案的部分代码。

我是一名新程序员，正在学习斯坦福大学的 edX 算法课程。

其中一项编程任务是使用 Kosaraju 算法在具有约 1,000,000 个顶点的图上找到强连通分量。我的实现是从教科书的伪代码到 Python 的最基本的翻译，它在较小的图上运行良好，所以我认为它是正确的。

Python 的默认递归限制为 1000，它达到了限制。

我试过sys.setrecursionlimit(1000000)了，但这并没有帮助，而是我得到“进程完成，退出代码 -1073741571”，这是一个堆栈溢出。

我发现这两个页面用于增加堆栈大小限制，但不确定如何使用它们中的任何一个：设置堆栈大小、ulimit 命令。

另一个相关的信息是 Python 没有优化尾递归，但我不确定它是否适用于我的代码。

我目前正在学习 Kleinberg 和 Tardos 在《算法设计》一书中展示的不同算法。我已经完成了 Kosaraju-Sharir 算法的实现，现在我正在尝试构建一个基于强连接组件的内核 DAG。我不确定如何实现将执行此操作的代码。目前，我有一个名为 display 的方法，它将打印强连接的组件，我希望它也能够打印内核 DAG。在此代码中，相邻是我的邻接列表，DFS 已经在反向邻接列表上执行。变量“kern”只是初始邻接列表的一个副本，它以如下所示的格式输入。我希望输出内核 DAG 看起来相似，

具有给定输入的以下方法的输出如下所示：

我试图为这个问题编写伪代码。我知道，由于我有强连接组件，我可以创建一个 for 循环，该循环将遍历各个强连接组件中的每个顶点，并在原始邻接列表中查找将其连接到另一个 SCC 的边。另外，我相信最好的做法是实现一个哈希图来存储内核 DAG，然后在打印之前检查该哈希图是否有重复项。这会是创建内核 DAG 的最佳和最干净的方法吗？还是我缺少更好的解决方案？

为什么我们要创建图形的转置，然后在第二遍中在转置上运行 dfs。我尝试在线阅读正确性证明http://www.jeffreykarres.com/blog/kosaraju/但无法理解是有一些替代方法可以做到这一点，这很容易理解

这是我的算法实现，它将顶点和边的数量作为输入，然后将有向边作为输入（顶点编号为 0 到 n-1）

我有大约 10k 个顶点的未加权有向图。

我想将图划分/聚类到某些组（强连接组件/聚类（？））。同时我想最小化这些组/组件的数量。我不想有数量为 1 或 2 等的组。

我认为相关的算法可能是这个;聚类/划分的基础; 算法：

• 科萨拉茹
• 塔里扬

我考虑首先使用 Kosaraju 并通过相互计数“组依赖关系”来连接 Kosaraju 的结果。

例如：我可以取最小的组并计算该组与休息之间的关系。选择最大相关组并与这个最小的组连接，依此类推。

你们堆垛机有没有其他方法，可以帮助我解决这个问题的想法？谢谢你的帮助。

编辑：强连接组件方法是错误的，它们并不多。

希望有人在这里有所了解。Kosaraju 算法实现的前半部分，带有图形和节点类。我正在遍历一个节点列表，每个节点都有一个头列表和一个尾列表，以允许向前或向后移动。当您在 Graph 中移动时，新探索的顶点是explored，然后您访问head_list：

有趣的是，i.head_list有时它是一个空列表，尽管在 Graph Test Data中每个节点都至少有一个头和一个尾。

示例（来自下面的测试数据）：第一次调用应该是 '9'，其中 ahead_list为 [6]，但返回 [] 并且tail_list是 [3, 7]。在调试钻入变量 3 作为 th 的一部分时tail_list，head_list填充有 [9] 但是tail_list[]。填充头部和尾部列表之间的某种翻转。

我以为有一些全局变量混淆了，但我还没有找到。我想也许 copy.deepcopy 可能已经修复了它，但事实并非如此。这似乎是非常不寻常的行为。更有趣的是，它似乎只在节点已经包含在head_list. 例如：节点 4 是第一个失败的节点，并且

我希望能够无限期地通过节点和head_list's 或tail_list's 连续钻取，但是迭代中列表的存在会改变银行和来回。任何见解将不胜感激。

测试数据

我正在尝试实现 Kosaraju 的算法，以在线性时间内找到有向图的强连通分量。目标是存储和输出 SCC 大小列表。

此代码为较小的图生成正确的输出（例如 9 个节点，15 条边）

但需要很长时间才能处理更大的图表。我该如何优化呢？