Please subscribe to the official Codeforces channel in Telegram via the link: ×

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


i have implemented code for the problem and the complexity is O(N2),but getting TLE. Any idea what is the best complexity for this problem