Graph problem - Codeforces

→ Pay attention

Before contest
Codeforces Round 1006 (Div. 3)
3 days
Register now »

→ Top rated

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	157
6	Qingyu	156
7	djm03178	151
7	adamant	151
9	luogu_official	150
10	awoo	147

View all →

→ Find user

→ Recent actions

Detailed →

Harta's blog

Graph problem

By Harta, 15 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
15 years ago
7

Comments (6)

Show archived | Write comment?

Oleg

15 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

15 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

15 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	15 years ago, # ^ \| +1 btw you can test algorithm with http://www.spoj.pl/problems/CYCLERUN/ after. → Reply

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

simp1eton

15 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