单连通图？

Question

单连通图是有向图，从 u 到 v ∀ u,v. 最多有 1 条路径。 我想到了以下解决方案：

从任意顶点运行 DFS。

1. 现在再次运行 DFS，但这次从顶点开始，按照完成时间递减的顺序。仅对先前某些 DFS 中未访问过的顶点运行此 DFS。如果我们在同一组件中发现交叉边或前向边，则它不是单连接的。
2. 如果所有顶点都完成并且没有这样的前向边的交叉，则单连接。
O(V+E)

这是对的吗？或者有更好的解决办法吗

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

Answer 1

在同一个组件中，当你进行DFS时，你会得到一条从一个顶点到另一个已经完成搜索的顶点的道路（当它被标记为黑色时）
当一个节点指向另一个组件>=2个顶点时，如果这2个顶点有连接，那么它就不是单连接的。但这需要您保留深度优先的森林。

Answer 2

每个节点至少有一些链接（传入或传出），同一组件中的每个节点至少有一个节点。 我们需要做的就是检查同一个组件是否存在这样的链接。

单连通分量可以计算如下：

将图转换为其无向图

• 运行DFS并设置每个节点的共同领导者
对所有节点运行迭代。 如果所有节点都有相同的公共领导者，则该图的无向版本是单连接的。

否则，它包含由相应领导者表示的多个单连接子图。

Answer 3

如果我们从初始顶点沿着两条不同的简单路径遇到相同的顶点，则该图不是单连通的。相反，如果我们发现任何初始顶点都没有这种情况，则该图是单连通的。

    def DFS(self, node: int, visited: List[int]) -> None:
        """
        Performs DFS on the graph
        """
        visited[node] = 1
        for neighbour in self.nodes[node]:
            if self.SC_ORIENTED == 0:
                return
            if visited[neighbour] == 2:
                self.SC_ORIENTED = 0
                return
            if visited[neighbour] == 0:
                self.DFS(neighbour, visited)
        visited[node] = 2

    def is_SC_oriented(self) -> bool:
        """
        self.nodes: dict with nodes as keys and set of its neighbours as values
        """
        if len(self.get_undirected_edges()) != 0:
            raise Exception("Graph is not undirected!")
        self.SC_ORIENTED = -1
        visited = [0]*len(self.nodes)
        for node in self.nodes:
            if visited[node] == 0:
                self.DFS(node, visited)
                if self.SC_ORIENTED == 0:
                    return False
        return True

该算法运行时间为 O(V*E)。
在下面的论文中可以找到一种在 O(V^2) 时间内运行的更高效的算法。

亚当·L·布赫斯鲍姆和马丁·C·卡莱尔。确定有向图中的单连通性。信息处理快报，48(1):9–12，1993。

Answer 4

这样对吗？

不，这是不对的。考虑下图，它不是单连接的。第一个分量来自从顶点 b 开始的 dfs，第二个分量来自从顶点 a 开始的 dfs。

正确的：

---

进行DFS，如果满足以下三个条件，则该图是单连通的：

无前缘

1. 同一组件中没有交叉边
2. 任意两个组件之间的交叉边不超过 1 个