Directed graph: Faster algorithm finding areas with only one "entrance"
<p>I have a directed graph consiting of objects each knowing the objects pointing at it and the objects it points to (m:n).
I have one object beeing the start node.
I am searching areas with only one entrance. These areas may contain loops and branches and such. The only condition is that you can not enter these areas from outside without passing one specific node.</p>

<p>I developed a simple algorithm solving this problem:</p>

<p>foreach node beeing a branch<br>
{<br>
    Mark all nodes which can be reached from the current one<br>
    Unmark all marked nodes, at which a node not beeing marked points, until there are no more such nodes<br>
}  </p>

<p>The problem is:
it gets really, really slow is there are more than 1000 nodes with lots of branches, so the program freezes for some seconds or so and if i stop it using a debugger it is always executing this particular algorithm. This is a problem in special cases but i am going to automate it, so i want it to be fast.</p>

<p>The bad performance is not really surprising, because if there is a branch at start which re-unites after 5 nodes the first 995 nodes are marked and 990 unmarked again one by one.
:( But i have no better idea.</p>

<p>Is there any way of solving this problem faster?</p>

<p>Info about the graphs: Most nodes (about 80%) are just links having exactly one predecessor and one following node, but throwing these away is a really bad idea, because i need them later. Also i am working with the objects in memory, so there are some slight modifications (replacements, removing and adding link nodes)</p>
