强连通分量
有向图中的两个不同的顶点是强连通的，如果图中有路径从每个点到另一个点。图的强连通分量是图的子集，因此子集中的每一对不同的顶点都是强连通的，并且向子集添加任何更多的顶点都会破坏该属性。
您的挑战是将一个图分离成其强连通的组件。具体来说，您必须输出图表中的所有SCC。
I/O:
作为输入，您可以使用有向边列表、邻接列表、邻接矩阵或任何其他合理的输入格式。问问你是不是不确定。你可以假设这个图没有完全不连通的顶点，并且没有自己的边，但是你不能做任何进一步的假设。您还可以选择将顶点列表作为输入，以及顶点的数量。
作为输出，您必须给出顶点的分区，例如一个顶点列表，其中每个子列表是一个强连接的组件，或者一个顶点的标记，其中每个标签对应于一个不同的组件。
如果使用标号，标签必须是顶点，或者是连续的整数序列。这是为了防止将计算浪费到标签中。
示例：
这些例子采用边的列表，其中每个边从第一个条目定向到第二个条目，并输出分区。您可以自由使用这种或另一种格式。
输入在第一行，输出在第二行。
[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]
[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]
[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]
[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]评分和限制：
标准漏洞和往常一样被禁止。此外，专门处理强连接组件的内置也被禁止。
对于所提供的示例，解决方案的运行时间不应超过一个小时。(这是为了防止缓慢指数解，而不是其他。)
这是暗号高尔夫。最少字节占上风。
回答 2
Code Golf用户
发布于 2016-03-27 09:17:20
Pyth，13字节
.gu+Gs@LQG.{k输入是一个邻接列表，表示为一个字典，它将顶点映射到它有边的顶点列表(它的有向邻居)。输出是一个分区。
程序的本质是，我们找到从每个顶点可以到达的顶点集，然后根据这些集合对顶点进行分组。在同一个SCC中的任何两个顶点都有可从它们访问的同一组顶点，因为每个顶点都是可从另一个到达的，并且可达性是可传递的。不同组件中的任何顶点都有不同的可访问集，因为它们都不包含其他集合。
代码解释：
.gu+Gs@LQG.{k
Implicit: Q is the input adjacency list.
.g Q Group the vertices of Q by (Q is implicit at EOF)
u .{k The fixed point of the following function,
starting at the set containing just that vertex
+G Add to the set
s The concatenation of
@LQG Map each prior vertex to its directed neighborsCode Golf用户
发布于 2016-03-26 12:34:24
JavaScript (ES6)，125个字节
a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))将有向对的列表作为参数，而结果是每个顶点的数组，给出与其强连接的第一个顶点，我认为这是一个有效的标签。例如，对于输入[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]，它返回[, 1, 1, 3, 3, 1, 6, 6, 3] (没有顶点0；顶点1、2和5有标签1；3、4和8有标签3，而6和7有标签6)。
https://codegolf.stackexchange.com/questions/76299
复制相似问题
腾讯云开发者
