Форум программистов, компьютерный форум CyberForum.ru

Поиск неориентированного графа - C++

Восстановить пароль Регистрация
 
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
22.09.2010, 22:07     Поиск неориентированного графа #1
Здравствуйте, мне надо бы очень срочно решить данную задачу:

Даны степени вершин неориентированного графа. Гарантировано, что число ребер в графе не превышает 500 000. Граф не содержит циклов и петель

Формат входных данных
Первая строка содержит число N-количество вершин в графе (1<=N<=10 000). N чисел? записанных в следующей строке [I]d[i] (1<=d<=10 000) описывают степени i-той вершины графа. Числа разделены запятыми.

Формат выходных данных
Выведите "YES" если такой граф существует, иначе "NO"

Если такой граф существует, то при выводе "YES", вывести число M - количество ребер в графе. В следующих M строках номера вершин, которые соединяет ребро.

Пример
ВВОД
4
2 1 2 3

ВЫВОД
YES
4
4 3
4 1
4 2
3 1

Добавлено через 4 часа 59 минут
Ну кто нибудь, мне надобы завтра сдать...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.09.2010, 22:07     Поиск неориентированного графа
Посмотрите здесь:

C++ поиск центра графа
C++ Поиск кратчайших путей из одного источника для неориентированного графа
Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа C++
C++ По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа
Обход неориентированного графа в ширину. В конце выдаёт путь: 1 C++
Напишите алгоритм вывода списка ребер неориентированного графа C++
Обход неориентированного графа в глубину C++
C++ K-связность неориентированного графа

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 23:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru