单连接图？ [英] Singly connected Graph?

问题描述

一个单连通图是一个有向图，它最多有 个从u到v∀u，v的路径。

A singly connected graph is a directed graph which has at most 1 path from u to v ∀ u,v.

考虑以下解决方案：

1. 从任何顶点运行DFS。


2. 现在再次运行DFS，但这一次是从顶点开始，以减少完成时间的顺序。仅对某些先前的DFS中未访问的顶点运行此DFS。如果在同一组件中找到交叉边缘或在前边缘中，则该交叉边缘不是单个连接的。


3. 如果所有顶点均已完成且前边缘没有交叉，则将它们单独连接。

O（V + E）

这是对的吗？还是有更好的解决方案。

Is this right? Or is there a better solution.

更新：最多1条简单路径。

Update : atmost 1 simple path.

推荐答案

如果满足以下两个条件之一，则图不会单独连接：

A graph is not singly connected if one of the two following conditions satisfies:

1. 在同一组件中，当当您执行DFS时，您会得到一条从一条顶点到另一条已经完成搜索的顶点的路径（当标记为BLACK时）

1. In the same component, when you do the DFS, you get a road from a vertex to another vertex that has already finished it's search (when it is marked BLACK)

当节点指向时到来自另一个组件的> = 2个顶点，如果2个顶点具有连接，则不会单独连接。但这需要您保留深度优先的森林。

When a node points to >=2 vertices from another component, if the 2 vertices have a connection then it is not singly connected. But this would require you to keep a depth-first forest.

这篇关于单连接图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！