在有向图中查找可从所有其他节点访问的节点

Question

问题：

给定一个包含 N 个节点和 M 条边的有向图 (M <= 2.N)。找到所有其他节点可达的所有节点。

示例：

下图有 4 个节点和 4 个边：

答案： 节点 (2) 和 (3) 可以从所有其他节点到达节点。

P/S:

我想出的唯一解决方案是还原图形，BFS 所有节点并检查它们是否到达所有其他节点。但这需要 O(n^2).

是否有任何其他方法需要 O(n.logn) 或更少？

这是我对 O(n^2) 方法的看法：

void init(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[v].emplace_back(u);
    }
}

void dfs(int u){
    visited[u] = true;
    for(int v : adj[u])
        if(!visited[v]) dfs(v);
}

init();
for(int u = 1; u <= n; u++){
    memset(visited, 0, sizeof visited);
    dfs(u);
    if(count(visited + 1, visited + n + 1, 1) == n) cout << u << ' ';
}

Answer 1

你能分享那个需要 O(n^2) 的代码吗？

无论如何，这种方法只需要 O(n)，比 O(n log n) 更好！

class DirectedGraph {
    graph = {}
    constructor(directedGraph) {
        for (let [id, arrow] of directedGraph)
            this.graph[id] = { arrow, isVisited: false }
    }
    find_end_points(id) {
        let out = [], graph = this.graph;
        function go_next(id, from) {
            let node = graph[id];
            if (node.isVisited || !node.arrow) return out.push(id)
            if (node.arrow == from) out.push(id);
            node.isVisited = true;
            go_next(node.arrow, id);
        }
        go_next(id, null);
        return out
    }
}
let directedGraph = new DirectedGraph([[2, 3], [3, 2], [1, 2], [4, 1]]);
console.log(directedGraph.find_end_points(4))

Answer 2

您可以使用 Tarjan's strongly connected components algorithm. Many sample implementations are available online 或标准算法教科书中的 O(|V| + |E|) 算法。

一旦你有了强连通分量，所有其他顶点可达的顶点集就是强连通分量的出度为 0 的顶点集（图中的汇）。但是，有一个例外：如果图的凝聚（由强连通分量导出的新图）不连通，则不存在这样的顶点。您可以在 O(|V|) 时间内通过运行从任何入度为 0 的顶点进行广度优先搜索来测试有向无环图的连通性。

在有向图中查找可从所有其他节点访问的节点

Find nodes in directed graph that is reachable from all other nodes

algorithm

graph

directed-graph