Harta's blog

By Harta, 8 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
 
 
 
 

8 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.
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello,

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