Найти - Пользователи
Полная версия: Проверка на полный граф
Начало » Python для новичков » Проверка на полный граф
1
T0t0ro
Неориентированный граф с кратными рёбрами называется полным, если любая пара его различных вершин соединена хотя бы одним
ребром. Для заданного списком ребер графа проверьте, является ли он полным.
Входные данные
Сначала вводятся числа n ( 1≤n≤100) – количество вершин в графе
и m ( 1≤тm≤10000) – количество ребер. Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите «YES», если граф является полным, и «NO» в противном случае.
Примеры входные данные
5 18
1 2
1 3
1 3
1 4
1 4
1 4
1 5
1 5
2 3
2 4
2 4
2 5
3 4
3 4
3 4
3 5
3 5
4 5
выходные данные
YES
py.user.next
Тут надо прочитать всё в словарь, у которого элементами являются пары (int, set) - это вершина и множество вершин, с которыми она соединена ребром. При этом при считывании каждой пары нужно и левый элемент делать ключом словаря, и правый элемент делать ключом словаря.
После считывания надо пройти по словарю и для каждого ключа проверить длину множества.
Ключей в словаре должно быть n и длина каждого множества должна быть n. Количество ключей в словаре, как и длина множества, определяется функцией len.

Пример определения длин на произвольном словаре
  
>>> d = {1: {1, 2, 3}, 2: {3, 4, 5, 6}}
>>> d
{1: {1, 2, 3}, 2: {3, 4, 5, 6}}
>>> len(d)
2
>>> len(d[1])
3
>>> len(d[2])
4
>>> 
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB