CrazzyBeer's blog

By CrazzyBeer, 9 years ago, translation, In English

Hello.

Suppose we have a undirected graph V. We certainly know that any vertex u can be reached from any vertex v.

If we delete vertex K and it's edges and, therefore, any vertex u losses connection with any vertex v, then K is considered to be important.

So we need to find the number of this important vertexes.

First that comes to mind is DFS, but I think there are other faster ways to solve this problem.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is just the number of critical vertexes in a graph. The idea is to use Trajan's algorithm.