Graph problem - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:55:57
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

Harta's blog

Graph problem

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

graph

Harta
14 years ago
7

Comments (6)

Show archived | Write comment?

Oleg

14 years ago, # |

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.

See proof and algorithm how to find all its cycles here http://books.google.com/books?id=pSnp4n0Nv3UC&pg=PA39&dq=Tournament+Graph.+pancyclic&hl=ru&ei=2KEkTNDrO43-_Abr19TIBA&sa=X&oi=book_result&ct=result&resnum=6&ved=0CEMQ6AEwBQ#v=onepage&q=Tournament%20Graph.%20pancyclic&f=false

→ Reply

Harta

14 years ago, # ^ |

Thx for replying, well I understand the proof that every strongly connected tournament of order v(>=3) is vertex-pancyclic, but I still don't understand how to find the set of cycle of size K. Could you elaborate more?
Thanks for your attention.

→ Reply

Oleg

14 years ago, # ^ |

So we use induction step from proof to fiind it for K - first we search for size 3 then 4,5,6..K.

Here another link for proof with better quality

http://books.google.com/books?id=LgZKLPRH2D4C&pg=PA125&dq=Tournament+Graph.+pancyclic&hl=ru&ei=eAAlTPe1Mo___AaTpdTIBA&sa=X&oi=book_result&ct=result&resnum=8&ved=0CE0Q6AEwBw#v=onepage&q=Tournament%20Graph.%20pancyclic&f=false

→ Reply

Oleg	14 years ago, # ^ \| +1 btw you can test algorithm with http://www.spoj.pl/problems/CYCLERUN/ after. → Reply

Oleg	14 years ago, # ^ \| 0 btw you can test algorithm with http://www.spoj.pl/problems/CYCLERUN/ after. → Reply

simp1eton

14 years ago, # ^ |

Hi,

Sorry, it seems that the left side of the page is cut off for me, and therefore I cannot really read what the proof is about.

From what I gathered from the page and googled about, if a tournament of size N is strongly connected, then it is vertex pan-cyclic, which means that every vertex in G is part of a cycle of length K for 3<=K<=N. And this proof is done using induction.

However, as the page is cut off, I cannot really read it, and I think I don't really understand what I read too XD. Is it okay for you to explain it here? Is the proof and algorithm similar to the proof and algorithm for finding a hamiltonian path in a tournament? I tried to adapt that algorithm and it seems that I got into some counterexamples.

→ Reply