问题标签 [tarjans-algorithm]

我目前正在为大学做一个挑战，在那里我必须获得有向图（没有循环，没有多重边）的拓扑排序（如果它是 DAG）或获得强分量（如果它不是 DAG）。Tarjans 算法似乎是最好的，因为它以相反的拓扑顺序找到图的所有强分量。如果图是一个 DAG，它会找到所有顶点的逆拓扑排序，因为 DAG 中的每个顶点都是它自己的 SCC。问题是tarjans alg的拓扑类型。在 DAG 上并不总是适合标准顶部的那个。排序（问题末尾的那个）找到，这让我的大学提供的所有测试都失败了。

这方面的一个示例是具有 8 个顶点和以下边的 DAG 在此示例中为支架。最佳。排序算法。不会创建相同的顶部。排序为 tarjan alg。

0 -> 4

1 -> 6

2 -> 1

3 -> 1

5 -> 6

6 -> 4

7 -> 3

问题是是否有可能始终获得拓扑排序标准的顶部。sort 从修改后的 tarjan 返回以及该修改的外观。Tarjans O(v+e) 不应该通过修改来改变。

我知道我可以同时实现两者，但挑战在于性能，所以我更希望有一种算法可以同时实现。

我目前正在维基百科上使用 tarjans 实现 https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

这是立场。用于我的大学提供的测试的顶级排序算法

这个算法总是从顶点 0 开始。顶点它总是采用最低的 adj。首先是顶点（作为一个数字）。它会去 0 -> 1 然后 0-> 6

我希望你能帮助我，并提前谢谢你。

我很难理解 Tarjan 的关节点算法。我目前正在这里学习本教程：https ://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/ 。我真正看不到，在任何其他教程中也看不到的是“后边缘”的确切含义。考虑到那里给出的图表，我知道 3-1 和 4-2 是后边，但 2-1、3-2 和 4-3 也是后边吗？谢谢你。

我有 Tarjan 算法的以下（递归）实现，可以在图中找到强连接的组件，它工作正常：

但是在大图上，显然，递归版本会抛出 StackOverflowException。因此我想让算法非递归。

我试图DFS用以下（非递归）函数替换该函数，但该算法不再起作用。有人可以帮忙吗？

以下代码显示了测试：

有一个图和它所有的强连接组件，我想知道找到连接两个 SCC 的弧的最有效方法是什么。我找到的所有解决方案都涉及遍历所有节点，我想知道是否有办法在不这样做的情况下做到这一点，特别是在我用来在图中找到 SCC 的 Tarjan 算法期间。无论如何以线性方式进行？

非常感谢！

我目前正在做一个项目，我需要找出图中存在多少强连通分量（SCC），然后，我需要检查是否有任何边从任何 SCC 到另一个 SCC。

我正在使用 Tarjan 的算法，我已经可以从给定的图表中获取所有 SCC，但我无法计算下一部分。

我有两个想法：

1. 删除每个 SCC 内的所有边。唯一剩下的将是可能的候选人。
2. 不知何故，将每个 SCC 变成一个“顶点”或一个超级顶点，然后检查是否有到任何其他超级顶点的传出连接。

我唯一的限制是：

• 如果同一个 SCC 有多个连接，我只需要显示一次；

• 当我显示连接时，我需要始终显示属于 SCC 的最小顶点 id，无论是传出 SCC 还是传入 SCC。

一个小例子：

输入作为从 x 到 y 的边

1 2; 2 3; 3 1; 2 4; 4 5; 5 4;

这是上图的图像，其中 1 = A，2 = B 等等......

我的问题是：我如何计算这个？我似乎想出的每一个选择，似乎都太耗费时间和资源了。

感谢所有帮助:)

测试用例是：有3个顶点1,2,3这样

边缘：源-目的地

随着 dfs 从 1 到 2 再到 3 。以下是发现和低谷时期：

由于 2 的光盘时间小于 3 的低时间。由于不应该是的定理，2成为关节点。

难道我做错了什么 。请解释。下面是我的 dfs 函数->

所以我已经成功实现了一个递归 tarjan，它为我提供了一个图的 SCC

我的递归实现如下：

现在我需要将其转换为迭代解决方案。我已经检查了很多资源来帮助我，包括一个非常相似的 SO 问题（Tarjan 算法的非递归版本）。我不能使用枚举器，因为我必须处理长值并且当前状态的后继索引已存储在 Dictionary(SuccessorMap[]) 中（需要处理节点数 > 50 亿的图）。

我遵循了将递归解决方案转换为迭代解决方案的一般准则：

1. 将递归调用替换为推送到本地堆栈
2. 用本地堆栈中的弹出替换“返回”

3. 在循环开始时设置变量并从本地堆栈中弹出

   /li>

我认识到迭代方法中的 do-while 循环总是会抛出 a InvalidOperationException(stack empty)，但我还没有弄清楚迭代地实现递归 do-while 。

非常感谢任何帮助我的帮助。

这个问题与Leetcode 的“网络中的关键连接”非常相似。给定一个无向图，我们想要找到所有的桥。无向连通图中的一条边是一座桥，当且仅当当且仅当移除它会断开该图。

变体

我不想找到所有的桥梁，而是想最大化要删除的边数，以便图形保持连接。

示例 1

Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]

Output: 1

首先，我可以删除[3,4],[1,3]或[1,4]. 接下来，在去除 3 条边中的任何一条后，剩下的边都是桥。因此，为了使图保持连接，要删除的最大边数为 1。

示例 2

Input: n = 6, edges = [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [4, 6], [5, 6]]

Output: 2

我正在使用 Tarjan 算法在无向图中查找关键连接。然而，当输入有 100000 个顶点时，它有时会抛出一个 TLE。我四处寻找，找不到原因。

我试图实现 Tarjan 算法的迭代版本，但无法弄清楚。对代码有进一步的改进吗？

测试用例链接：https ://leetcode.com/submissions/detail/276043932/testcase/

继续问题：pyspark dataframe withColumn command not working

我有一个输入数据框：df_input（更新的 df_input）

如果您看到 inp_col 和 inp_val 具有层次结构，并且它可以是具有根值的 n 数。这里的父值是"b"和"a"。

现在，根据我的要求，我必须将以“&”开头的子值替换为其相应的值。我尝试迭代以 inp_val 列中的“&”值开头的值列表，并在每次迭代中替换为值列表。但是，它没有奏效。我面临如何获取包含父子列表值的列表的问题。

试过的代码：

更新的预期输出：

之后我可以尝试做爆炸以获得多行。但是，aove 输出是我们需要的，并且无法获得一定的百分比结果。