Graph problem - Codeforces

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2)
5 дней

→ Трансляции

CodeChef Starters 130 Solution Discussion

aryanc403

До начала 22:19:31

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	SecondThread	150
8	-is-this-fft-	149
9	pajenegod	145
10	BledDest	144

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Harta

Graph problem

Автор Harta, 14 лет назад, По-английски

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 лет назад
7

Комментарии (6)

Показать архивные | Написать комментарий?

Oleg

14 лет назад, # |

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

→ Ответить

Harta

14 лет назад, # ^ |

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.

→ Ответить

Oleg

14 лет назад, # ^ |

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

→ Ответить

Oleg	14 лет назад, # ^ \| +1 btw you can test algorithm with http://www.spoj.pl/problems/CYCLERUN/ after. → Ответить

Oleg	14 лет назад, # ^ \| 0 btw you can test algorithm with http://www.spoj.pl/problems/CYCLERUN/ after. → Ответить

simp1eton

14 лет назад, # ^ |

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.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 16.04.2024 21:25:29 (k2).

Десктопная версия, переключиться на мобильную.

При поддержке