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

Revision en1, by ayushmalik03, 2020-04-08 07:54:08

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 ?

Tags #dfs and similar, #cycle, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ayushmalik03 2020-04-08 07:56:34 2
en2 English ayushmalik03 2020-04-08 07:55:35 1 (published)
en1 English ayushmalik03 2020-04-08 07:54:08 579 Initial revision (saved to drafts)