Is it possible to detect cycle of length k in directed graph in O(max(V,E)) time ?

Правка en3, от ayushmalik03, 2020-04-08 07:56:34

Problem A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes u and v (u ≠ v) exists either an edge going from u to v, or an edge from v to u. You are given a tournament consisting of n vertexes. Your task is to find there a cycle of length three.

n<=5000;

. Instead of 3 , if it was k than how should we approach this problem ?

Теги #dfs and similar, #cycle, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ayushmalik03 2020-04-08 07:56:34 2
en2 Английский ayushmalik03 2020-04-08 07:55:35 1 (published)
en1 Английский ayushmalik03 2020-04-08 07:54:08 579 Initial revision (saved to drafts)