---> 54 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

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

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

Примеры
Входные данные
5 10
1 2
1 3
1 5
2 3
2 5
3 2
4 1
4 3
4 5
5 3
Выходные данные
NO
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)) – количество ребер. Затем следует m пар чисел – ребра графа.

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

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

Примеры
Входные данные
5 10
1 2
1 3
1 5
2 3
2 5
4 1
4 2
4 3
4 5
5 3
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует, что вершины u и w соединены ребром.

Проверьте, что заданный неориентированный граф является транзитивным.

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

Сначала вводятся числа n ( 1$ le$n$ le$100) – количество вершин в графе и m ( 1$ le$m$ le$n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.

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

Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры
Входные данные
5 1
2 5
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u, v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.

Проверьте, что заданный ориентированный граф является транзитивным.

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

Сначала вводится число n ( 1$ le$n$ le$100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

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

Выведите  «YES», если граф является транзитивным, и «NO» в противном случае.

Примеры
Входные данные
5
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задано описание метрополитена в виде описания веток. Каждая ветка содержит номера станций, которые на ней находятся. Станция, присутствующая на нескольких ветках - пересадочная. Требуется определить маршрут от станции до станции с минимальным количеством пересадок.

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до $N$. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции $A$ на станцию $B$. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции $A$ на станцию $B$ добраться невозможно, в этом случае ваша программа должна это определить.

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

Сначала вводится число $N$ — количество станций метро в городе (2≤$N$≤100). Далее следует число $M$ — количество линий метро (1≤$M$≤20). Далее идет описание $M$ линий. Описание каждой линии состоит из числа $P_i$ — количество станций на этой линии (2≤$P_i$≤50) и $P_i$ чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: $A$ — номер начальной станции, и $B$ — номер станции, на которую нам нужно попасть. При этом если через станцию $A$ проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию $B$ проходит несколько линий, то нам не важно, по какой линии мы приедем.

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

Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции $A$ на станцию $B$ невозможно, программа должна вывести одно число –1 (минус один).

Примеры
Входные данные
5
2
4 1 2 3 4
2 5 3
3 1
Выходные данные
0
Входные данные
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
Выходные данные
2
Входные данные
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
Выходные данные
1
Входные данные
4
2
2 1 2
2 3 4
1 3
Выходные данные
-1

Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест