Ами ако няма корен си е граф,макар че дървото си е граф така или иначе ако гледаме в тази посока. А в условието пише АКО няма корен, понеже със сегашната реализация на предното домашно за дърво (поне при мен) може да се получи така че дървото да стане без корен.

Да, така е. Можеш ли да дадеш пример за  такъв граф представен с формата на input-а от условието на задачата? Трябва да е с 2 компоненти на свързаност, но в никакъв случай не е дърво както е дано в условието. Странно е.

EDIT: Сетих се за такъв пример. Може би затова е дадена подобна задача - да се разгледа под друг ъгъл. Все пак дай такъв пример ако можеш. Примерите, за които се сещам всички са с 2 компонента на свързаност

Сега условията са много по-ясни наистинa. Единствено на първа задача не разбирам защо последните два примера не се вързват с условието - The nodes have unique integer numbers between 0 and N inclusive (т.е. N+1 възела са дадени). T.e. за N=3 би трябвало да иамме 4 възела {0, 1, 2, 3} докато в примера са дадени 3 възела {0, 1, 2} . Излиза, че понякога може да имаме N + 1 възела, а в други случаи N.

Във втора задача, ако приятелствата са двупосочни, отговорът на втория пример не трябва ли да е 4 (7->1->4->5)?

По идея е абсолютно същата като Distance in Labyrinth в темата за листовете, но не ходиш в 4 посоки, а имаш достъп до най-много 8, както и до всяко поле на матрицата. Някрая просто отпечатваш средната колона по целочислено деление.

Ясно, "съседните", както пише в задачата, полета са въпросните 8.

Благодаря ти!

Да, точно. 8-те по хода на коня.

Наистина първа задача е доста двусмислена. Твоят алгоритъм има малък пропуск в случая "Forest is not a tree". Ако въведеш например следния вход:

4
0 1
1 0
1 1
2 3

ще ти изкара 2 като root, а това всъщност са два графи (графа?).

Вчера се мъчих да я натъкмя доста дълго, и в крайна сметка я оставих за "някой друг път". Ще се радвам, ако някой, който го е измислил как да стане си сподели решението ;)

Благодаря за наблюдението. Това лесно може да бъде поправено като започнат да се търсят компонентите на свързаност, което едва ли е било идеята на тази задача. Просто не е доизмислена. Идеята да търсиш корен на дърво, което не е дърво е като да търсиш по черешово дърво банани или под краката на магарето корените му :) Затова не смятам да оправям този случай, въпреки че знам как да го направя.

Reverse-а и аз го решавам по подобен начин, но нямам проблем efficien за дадените примери. Може би забавянето не идва от в reverse-ванията. Ето решението ми: Sorting. Има още какво да се направи по него, възможно не всички ситуации да са обработени, но може да ти помогне да откриеш проблема. Ще е интересно да видя и твоето решение.

За последната задача със сортирането: можеш да пазиш поредица елементи като List<int>. За уникалността може да ползваш HashSet<string> и в него да слагаш поредицата във вид на стринг със запетайки, примерно "6,3,8,1". Така си гарантираш, че не повтаряш някои от поредиците.

Наков

@dim4o, гледам правиш нещо като хеш код и разчиташ той уникално да идентифицира поредицата. Това е хитро, но какво става ако имаме двуцифрени числа (N>=10). Може би да умножаваш по 100 и да пазиш резултата в 64-битов long?

Наков

По условие на задачата след като подадеш броя на edges следващите N реда въвеждаш двойка числа, първото за родител, второто за дете. Ако подадеш примерно 6 за броя на нодовете, следващите 6 реда биха били примерно:
1 2
1 3
2 4
2 5
3 6
6 7
По този начин корен се явява 1. Понеже 2 и 3 са деца на 1. По същата логика 4 и 5 са цеда на 2. А 6 е дете на 3, както и че 6 е родител на 7. И в този ред на мисли от 7 (крайно листо) мога да стигна до корена 1, (7>6>3>1), нали на обратно също. В изложения пример всички имат родител БЕЗ корена 1.
Та за да получиш "Forest is not a tree, трябва такива данни да подадеш, така че да имаш две отделни дървета. Ако използвам горния пример би било следното:
6 - за броя на нодовете
1 2
3
2 4
2 5
3 6
6 7
По този начин се получават два нода, които нямат родител, 1 и 3.
Демек от крайното листо 7 мога да стигна само до 3 (неговия корен)

Благодаря много!А за 6 имаш ли някаква идея, какво се желае, не съм доста добър с английския?

"1 5" означава, че има връзка между двата node-а

иначе можеш и 1 да си го изкараш като корен, няма да има значение, пак е същия отговорът (важното е, че листата си остават същите) : )

за първия ред и аз не съм сигурна, но попринцип в задачи се дават ограничения за това N и така знаеш колко памет ти трябва, дали ще имаш time limit и т.н.

Не би трябвало да е така, трябва ясно да е дефинирано кое е родител и кое дете, а във всички останали случаи във входните данни подредбата е правилна. В противен случай може всеки нод да разглеждаш като корен и няма да има начин да търсиш листата, понеже всеки нод ще има деца и родител; няма как да търсиш нодове без деца с тази дефиниция, защото такива просто няма.

И според мен е грешен входа. Ако беше така корена трябва да е 1, а не 5. Факт е, че решението може да работи и с този вход и да дава правилен изход, но определено не е коректно. Единствено не разбрах какво се очаква да направим по 1-ва задача. Там противоречията са много и няма как човек да си изгради единна теория за това как би могло да е коректното условие. Надявах се да се доизясни, но изглежда, че ще си остане така.