Нахождение дополнения графа
Дан неориентированный граф с
v вершинами и e рёбрами. Требуется найти его дополнение.Дополнение графа — это граф, в котором проведены рёбра между всеми теми вершинами, которые не соединены в исходном графе. При этом, в дополнении не должно быть рёбер между вершинами, которые имели ребро в исходном графе.
.png?table=block&id=18b2c681-664d-8121-a375-e4d1cdce54da&cache=v2)
Вход
Первая строка входных данных содержит два целых числа
v (1 ≤ v ≤ 500) и e (1 ≤ e ≤ 100 000).Следующие
e строк задают пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), где вершина v1 соединена с вершиной v2 (и наоборот).Выход
Программа должна вывести список смежности для дополнения графа. Каждая строка должна начинаться с идентификатора вершины, за которым следует двоеточие (
:), и далее перечисляются её соседи. Соседи в каждой строке разделяются пробелом. Порядок вывода вершин и их соседей не важен.Примеры
Вход | Выход |
4 4
1 2
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB