10317. Молочная фабрика

Молочный бизнес процветает! Завод по переработке молока фермера Джона состоит из n станций переработки, пронумерованных 1 .. n и n – 1 пешеходных переходов, каждый из которых соединяет две станции (переходы дорогие, поэтому фермер Джон хочет использовать минимальное количество переходов, чтобы можно было добраться с любой до любой станции).

Чтобы повысить эффективность, фермер Джон установил конвейерную ленту на каждом переходе. К сожалению, он слишком поздно понял, что каждая конвейерная лента движется только в одну сторону, поэтому теперь движение по каждой дорожке возможно только в одном направлении! Теперь уже не так, что можно путешествовать с любой станции на любую другую.

Однако фермер Джон считает, что не все потеряно, если имеется хотя бы одна такая станция i, что можно добраться до i с любой другой станции. Обратите внимание, что поездка на станцию i с другой произвольной станции j может включать в себя проезд через промежуточные станции между i и j. Помогите фермеру Джону выяснить, существует ли такая станция i.

Вход. В первой строке записано целое число n (1 ≤ n ≤ 100) – количество станций обработки. Каждая из следующих n – 1 строк содержит два целых числа a_i и b_i, где 1 ≤ a_i, b_i ≤ n и a_i ≠ b_i. Она означает, что существует конвейерная лента, которая движется от станции a_i к станции b_i, позволяя двигаться только в направлении от a_i к b_i.

Выход. Если существует станция i такая, что можно дойти до станции i с любой другой станции, то выведите минимальное значение i. В противном случае выведите -1.

Пример входа	Пример выхода
3 1 2 3 2	2

РЕШЕНИЕ

графы

Анализ алгоритма

Из условия следует, что граф является деревом. Истоком назовем вершину, в которую не входят ребра. Стоком назовем вершину, из которой не выходят ребра. В задаче следует найти минимальный номер вершины i, являющуюся стоком. Сток в дереве может быть один. Действительно, если имеется два стока – x и y, то должна существовать возможность добраться из x в y и из y в x. То есть в графе должен существовать цикл. А это невозможно для дерева.

Для каждой вершины i посчитаем количество входящих in[i] в нее и выходящих out[i] из нее ребер. Для того чтобы сток был единственным, необходимо и достаточно существование единственной вершины без исходящих ребер.

Пример

Граф, приведенный в условии, имеет один сток – вершину 2.

Реализация алгоритма

Объявим рабочие массивы.

#define MAX 101

int in[MAX], out[MAX];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n - 1; i++)

{

scanf("%d %d", &a, &b);

Для каждого ориентированного ребра (a, b) увеличиваем на 1 количество исходящих ребер из a и количество входящих ребер в b.

out[a]++; in[b]++;

}

В переменной cnt подсчитываем количество вершин без исходящих ребер.

cnt = 0;

for (i = 1; i <= n; i++)

if (out[i] == 0)

{

cnt++;

pos = i;

}

Если cnt = 1, то сток единственный, выводим его номер. Иначе требуемой вершины не существует, выводим -1.

if (cnt != 1) printf("-1\n");

else printf("%d\n", pos);