Re: Computing cut nodes and bridges in directed graphs

Give each edge unit weight and label it with an i->j max flow. If I am
reading your definition correctly all cutnodes will have an inflow
(outflow) equal to the outflow of i (inflow of j). All bridges will
themselves carry the same magnitude of flow.

I only realized after I wrote that you could use Ford Fulkerson, which
in this special case will run in O(|E|d) where d is the maximum of
indegree and outdegree of all nodes of the graph.

WIth some care, if you update the graph, you should be able to quickly
find a non-zero feasible flow and start augmenting from there. This
ought to yield updates quicker than augmenting from a zero flow at
least in the average case.

.