Harta's blog

By Harta, 9 years ago, In English,
I have a problem finding a strongly connected component of size exactly K in a Tournament Graph. Can someone help me?
Thanks in advance
  • Vote: I like it
  • 0
  • Vote: I do not like it

9 years ago, # |
  Vote: I like it +1 Vote: I do not like it
We can find cycle of length K (that obviously will be strongly connected component)

First find all strongly connected components in Tournament with classic O(N) 
if each component has size < K, there is no solution.

Check any component that has size >= K - it will be strongly connected tournament that  has all cycles from 3 to its size.
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it


i have implemented code for the problem http://www.spoj.pl/problems/CYCLERUN/ and the complexity is O(N2),but getting TLE. Any idea what is the best complexity for this problem