Graph problem - Codeforces

→ Pay attention

Before contest
Codeforces Round 1132 (Div. 2)
24:13:31
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	156
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	135
9	maroonrk	132
10	cry	130

View all →

→ Find user

→ Recent actions

Detailed →

Harta's blog

Graph problem

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

Comments (6)

Show archived | Write comment?

Oleg

16 years ago, hide # |

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

16 years ago, hide # ^ |

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

16 years ago, hide # ^ |

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

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

simp1eton

16 years ago, hide # ^ |

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

The only programming contests Web 2.0 platform

Server time: Nov/05/2026 17:21:30 (g2).

Desktop version, switch to mobile version.

Supported by