Блог пользователя bayram

Can anyone solve this problem?
Автор bayram, 12 лет назад, По-английски

Give an algorithm that determines whether or not a given undirected graph G =(V,E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|.

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Yes, they can

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    To be serious, the algorithm you know using dfs should work in O(V) time. Because until you find a cycle you will try only edges of the tree, so that is O(V).

    Another approach is |E| >= |V| => contains cycle, else O(E) = O(V), so you can do simple algorithm, too.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have you tried to google it?

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

If |E| >= |V| graph has a cycle. else you can use dfs. It would be in O(V).

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks everybody!

→ Ответить