Directed graph: Faster algorithm finding areas with only one "entrance"

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.

I developed a simple algorithm solving this problem:

foreach node beeing a branch

{

Mark all nodes which can be reached from the current one

Unmark all marked nodes, at which a node not beeing marked points, until there are no more such nodes

}

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.

The bad performance is not really surprising, because if there is a 开发者_Go百科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.

Is there any way of solving this problem faster?

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)

If I understood your situation correctly, you are looking for what is, in graph theory, called an articulation point or cut vertex. The Wikipedia page that is linked to describes a very efficient algorithm for detecting such points. Note that the algorithm is based on depth-first search, of which you should have a good understanding if you want to implement the algorithm. Also, if your graph contains many thousand nodes, you need to implement the depth-first search iteratively by using a stack, rather than recursively (which is the standard way of implementing it) - otherwise, your program will probably cause a stack overflow when given a large graph.