Graph problem - Codeforces

→ Pay attention

Before contest
Codeforces Round 1123 (Div. 2)
16:22:14
Register now »

*has extra registration

→ Streams

Codeforces Round 1123 Solution Discussion

By aryanc403

Before stream 18:47:14

View all →

→ Top rated

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

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: Sep/25/2026 01:12:46 (g2).

Desktop version, switch to mobile version.

Supported by