Граф з середини

Якось Ліса Сімпсон, персонаж мультсеріалу «Сімпсони», опинилася в одній з вершин деякого зв’язного неорієнтованого графа. Ліса може пересуватися між вершинами графа, які сполучено ребром, однак, окрім вершини, у якій вона на даний момент перебуває, а також усіх суміжних з нею вершин, дівчині нічого не видно. До того ж у Ліси нема з собою ручки та паперу, щоб занотовувати маршрут своїх пересувань або іншу інформацію. Зате вона має необмежену кількість камінців, які дівчина може залишати у вершинах графа, і саме цим вона планує скористатися, щоб дослідити деякі його властивості. На жаль, в одній вершині графа поміщається не більше ніж **1000 **камінців, але Ліса вірить, що цього їй вистачить. Відомо, що кількість вершин у графі не менша за 2 і не більша за 500.

Завдання

Дана задача складається з двох підзадач:

1. У першій підзадачі у жодній вершині графа спочатку немає камінців, а Ліса хоче з’ясувати, скільки вершин містить граф.

2. У другій підзадачі в одній з вершин графа (відмінній від початкової) лежить один камінець, а в решті вершин — жодного. Ліса хоче з’ясувати, якою є довжина найкоротшого шляху по ребрах між початковою вершиною і тією, де лежить камінець (якщо вважати довжину кожного ребра графа одиничною).

Напишіть процедуру graph, що за інформацією про кількість камінців у поточній вершині графа та всіх суміжних з нею вершинах визначає наступну дію Ліси: скільки камінців залишити в поточній вершині (або забрати з неї) і в яку з суміжних вершин піти далі; або, коли Ліса готова назвати відповідь на питання підзадачі, дає цю відповідь.

Деталі реалізації

Ви маєте надіслати файл, що містить реалізацію процедури graph, детально описану нижче, та, за потреби, інший код, необхідний для коректної роботи цієї процедури, але не містить самого тіла програми (тобто функції main у C++ або блоку begin/end. у Pascal). При тестуванні ваш файл буде доповнено спеціальним тілом програми, написаним журі. Тіло відповідним чином викликатиме написану вами процедуру та перевірятиме коректність алгоритму, який вона втілює. Реалізована вами процедура повинна мати такий вигляд:

C++: void graph(int subproblem, int neighborsCount, int neighbors[], int &current, int &whereToGo, int &answer);

Pascal: procedure graph(subproblem, neighborsCount: longint; var neighbors: array of longint; var current, whereToGo, answer: longint);

Параметри процедури

1. subproblem — номер підзадачі: 1 для підзадачі визначення кількості вершин, 2 для підзадачі пошуку довжини найкоротшого шляху.** **Номер підзадачі не змінюється під час запусків процедури на одному й тому ж графі.

2. neighborsCount — кількість суміжних вершин, тобто кількість вершин, сполучених з поточною вершиною ребром.

3. neighbors — масив, що містить рівно neighborsCount елементів (індексація з нуля) — кількості камінців у суміжних вершинах. Зверніть увагу, що порядок суміжних вершин може бути різним (довільним чином переставленим) під час різних викликів процедури, навіть якщо поточна вершина є однаковою. Вміст цього масиву процедура в разі потреби може змінювати, однак на реальній кількості камінців у відповідних вершинах це ніяк не позначається: Ліса може змінювати кількість камінців виключно в тій вершині, де вона на даний момент перебуває.

4. current — кількість камінців у поточній вершині. Цю кількість у процедурі можна змінити (як збільшити, так і зменшити, але так, щоб кількість не стала від’ємною або більшою за 1000). При цьому зміниться й реальна кількість камінців у відповідній вершині графа.

5. whereToGo — початкове значення цього параметра (аргумент, який передає тіло програми) дорівнює -1. Якщо Ліса продовжує дослідження графа, це значення слід переписати, зробивши рівним кількості камінців у вершині, куди Ліса повинна піти далі (зверніть увагу: це не індекс в масиві neighbors, а значення!). Якщо в масиві neighbors є відразу кілька елементів, що мають таке значення, то Ліса піде в одну з відповідних вершин, але те, в яку саме, процедура обмежити не може. Якщо Ліса на даному виклику процедури вже готова дати відповідь, початкове значення -1 цього параметра переписувати не потрібно (і не можна).

6. answer — початкове значення цього параметра (аргумент, який передає тіло програми) також дорівнює -1. Якщо Ліса готова дати відповідь, це значення слід переписати, зробивши його рівним відповіді. Якщо Ліса на даному виклику процедури ще не готова дати відповідь, початкове значення -1 цього параметра переписувати не потрібно (і не можна).

На кожному кроці процедура повинна визначати дії дівчини, виходячи виключно з даних, переданих їй на цьому кроці. На результат роботи процедури жодним чином не повинна впливати попередня взаємодія тіла програми та процедури. Крім того, процедура повинна бути детермінованою, тобто для сталих вхідних даних завжди повертати одні й ті самі значення.

Власноручне тестування

В електронному варіанті умов наведено приклад основного тіла програми graph_tester.cpp/graph_tester.pas, що запускає процедуру graph на графі, заданому у створеному вами вхідному файлі, і виводить відповідь, повернену процедурою, у вихідний файл. Щоб використати цю програму, розташуйте її в одному каталозі з файлом graph.cpp/graph.pas, який містить вашу реалізацію процедури, та створіть у цьому ж каталозі файл graph.dat зі структурою, описаною в наступному абзаці. Зауважте, що основне тіло програми, яке буде використано для оцінювання вашої процедури, відрізнятиметься від наданого вам у graph_tester.cpp/graph_tester.pas прикладу.

graph_tester: вхідні дані

Перший рядок містить чотири цілих числа. Перші три — кількість N вершин графа, кількість M ребер графа та номер початкової вершини. При цьому вважаємо, що вершини графа занумеровано натуральними числами від 1 до N. Четверте число дорівнює 0, якщо ви тестуєте процедуру на першій підзадачі, або дорівнює номеру вершини, в якій лежатиме один камінець, якщо ви тестуєте процедуру на другій підзадачі. Наступні M рядків файла задають ребра графа: по два числа в рядку у довільному порядку — номери сполучених ребром вершин.

graph_tester: вихідні дані

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

Оцінювання. Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:****

1. 30 балів: номер підзадачі — 1, граф є деревом.

2. 20 балів: номер підзадачі — 1, граф не обов’язково є деревом.

3. 10 балів: номер підзадачі — 2, граф є деревом.

4. 40 балів: номер підзадачі — 2, граф не обов’язково є деревом.

Зауваження. Якщо під час тестування на сервері написана вами процедура порушить описані вимоги, діагностикою може бути зокрема помилка виконання (runtime error) або помилка компіляції. Обмеження на пам’ять у цій задачі явно не задано, але ви можете сподіватися принаймні на 16 МБ. Користування глобальними змінними не забороняється.

Приклади