Harta's blog

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

| Write comment?
14 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.