--->
54 задач
<---
Источники
Ориентированный граф называется полуполным, если между любой парой его различных вершин есть хотя бы одно ребро. Для заданного списком ребер графа проверьте, является ли он полуполным.
Сначала вводятся числа 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
Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.
Сначала вводятся числа 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
Напомним, что граф называется транзитивным, если всегда из того, что вершины 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
Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин 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 до \(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