e-olymp 2270. Поиск цикла

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

Входные данные

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

Входные данные

Выходные данные

1
2 2
1 2
1 2
NO
2 2 2
1 2
2 1
YES
1 2
3 4 4
1 4
2 3
3 2
1 4
YES
2 3
4 6 6
1 3
2 4
3 4
1 2
3 5
3 6
NO
5 4 4
1 3
4 2
2 3
3 4
YES
4 2 3

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем «красить» вершины в различные цвета ($1$ (белый) — мы еще не посещали вершину, $2$ (серый) — посетили вершину и зациклились, $3$ (черный) — посетили вершину и вышли из неё).

В векторе $M$ будем хранить сам граф, а для самой проверки на цикличность воспользуемся векторами $visited$ и $colours$, в первом будем отмечать посещали ли мы вершину ранее или нет, во втором же изначально будут хранится только $1$
(белые) вершины, далее, по мере поиска, они будут приобретать другие цвета. И если мы захотим посетить $2$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине.

Осталось лишь вывести его на экран. Для этого ищем вершины, цвет которых $2$
(серый), так как нам достаточно вывести хотя бы один цикл, то для первой встретившейся вершины, в которой есть цикл, выведем вторую вершину.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

e-olymp 4852. Кратчайшее расстояние

Задача взята с сайта e-olymp.

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

Входные данные

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

Выходные данные

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

# Входные данные Выходные данные

1

3 3

0 1 1

1 0 1

1 0 0

1 2 0

2

6 5

0 1 1 0 0 0

1 0 0 0 0 0

1 1 0 0 0 0

0 0 0 0 1 0

0 0 1 1 0 0

0 1 0 0 0 0

2 2 1 1 0 -1

3

3 1

0 0 0

0 0 1

1 1 0

0 -1 -1

Код

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве  graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q  будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

e-olymp 5073. Проверка на наличие параллельных ребер (ОГ)

Ориентированный граф задан списком ребер.

Проверьте, содержит ли он параллельные ребра.

Входные данные

Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex]  — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные

Выведите в выходной файл YES если граф содержит параллельные ребра и NO в противном случае.

Задача на e-olimp. Ссылка на засчитанное решение.

Входные данные Выходные данные
3 4
1 2
2 3
1 3
2 1
NO
3 4
1 2
2 3
1 3
2 3
YES

Код задачи:

Ссылка на ideone.

Алгоритм решения:

Сначала, добавим пару вершин в разные массивы так, чтоб нулевой элемент массива [latex]v[i][/latex] был началом ребра, а нулевой элемент массива [latex]g[i][/latex] — концом ребра и т.д. После этого в цикле будем сравнивать поочередно пары вершин до тех пор, пока не узнаем, что такая пара вершин уже встречалась, в таком случае выводим YES и завершаем цикл. В противном случае, если наше условие не выполнилось ни разу (т.е. переменная [latex]k[/latex] как была нулем в начале программы, так и осталась) выводим NO.

Код на Java

 

e-olymp 5072. Подсчет количества ребер (ОГ)

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

Входные данные

Входной файл содержит число n (1n100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно или 1 — его матрицу смежности.

Выходные данные

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30  1 11 0 1

0 1 1

6
50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

9
21 11 1 4

Алгоритм решения прост. Количество ребер ориентированного графа равно  количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

e-olimp 5077. Полуполный граф

Задача: Полуполный граф

Решение

ссылка на ideone, засчитанное решение на e-olymp

Решение на Java

ссылка на ideone, засчитанное решение на e-olymp

Идея решения

Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO».

e-olimp 5078. Турнир

Задача e-olimp.com №5078.

Ссылка на засчитанное решение (C++).

Ссылка на засчитанное решение (Java).

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

Входные данные

Входной файл содержит числа [latex]n \left(1\leq n\leq 100 \right)[/latex] — число вершин в графе и [latex]m \left(1\leq m\leq n\left(n-1 \right) \right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

Выходные данные

Выведите в выходной файл YES если граф является турниром и NO в противном случае.

Код программы (С++):

Java:

 

Алгоритм решения. Я завела матрицу смежности, единицы в которой встречается тогда и только тогда, когда из вершины, представимой номером строки, есть ребро в вершину, представимую номером столбца.

Далее программа пробегает цикл по матрице смежности выше главной диагонали (так как на самой диагонали могут быть лишь петли, а в условии оговорено, что вершины должны быть различны). Если в таблице встречается 1, то мы должны проверить, если ли ребро, обратное данному. Если нет — продолжаем, есть — говорим, что граф не турнир и завершаем работу программы. Если же у нас не встретилось 1, то мы проверяем, есть ли обратное ребро. Если его нет, то мы говорим, что связи между этими двумя вершинами не существует, а следовательно наш граф — не турнир (завершаем программу).

После того, как цикл полностью пройден, можно с уверенностью утверждать, что граф является турниром.