Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
1

Полный граф

24.03.2018, 22:17. Просмотров 762. Ответов 3

Для заданного списком рёбер графа проверить, является ли он полным.

Входные данные
Первая строка содержит число вершин n (1 ≤ n ≤ 100) и число рёбер m (1 ≤ m ≤ 10000) в графе. Затем идут m пар чисел - рёбра графа.

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


Прошёл дфсом и посчитал количество вершин, но проходит только половину тестов. В чём может быть подвох?

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var
a:array[1..100, 1..1000] of boolean;
visited: array[1..1000] of boolean;
kol, i, n, s, j, x, y, m:longint;
 
procedure dfs(v:longint);
var i:longint;
begin
  inc(kol);
  visited[v]:=true;
  
  for i:=1 to n do
    if (a[v, i]) and (not visited[i]) then dfs(i);
end;
 
begin
readln(n, m);
for i:=1 to m do
begin
readln(x, y);
a[x, y] := true;
a[y, x] := true;
end;
 
dfs(1);
 
if kol=n then  writeln('YES') else writeln('NO');
end.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2018, 22:17
Ответы с готовыми решениями:

Полный перебор
Всем привет. Когда у нас есть фиксированное количество переменных и для них есть фиксированная...

Полный перебор
Добрый день. Возникла такая ситуация. Есть множество Х(други орграфа) и множество W(числа) и...

Обратный граф
Вот сама задача https://www.e-olymp.com/ru/problems/4854. Вот моё решение import...

Связный граф
Здравствуйте. У меня есть задача, в которой происходит работа со связными графами. Мне нужно...

полный перебор двоичного набора
Задача в следующем. Есть набор в котором строго N нулей и М единиц. Необходимо перебрать все...

3
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,422
25.03.2018, 01:22 2
Цитата Сообщение от Chvick Посмотреть сообщение
Первая строка содержит число вершин n (1 ≤ n ≤ 100) и число рёбер m (1 ≤ m ≤ 10000) в графе.
А в чём подвох? Зная количество вершин и количество рёбер, разве нельзя определить, полный граф или нет?
0
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
25.03.2018, 10:23  [ТС] 3
Shamil1, то есть вы хотите сказать, что полный - это не то же самое, что и связный?
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,422
25.03.2018, 19:50 4
Лучший ответ Сообщение было отмечено Chvick как решение

Решение

Цитата Сообщение от Chvick Посмотреть сообщение
это не то же самое, что и связный?
Да.
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.

Возможно, подвох в том, что некоторые вершины могут быть связаны несколькими рёбрами. Нужно просто заполнять булев массив, а потом проверить, остались ли в нём фолсы.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2018, 19:50

Как реализовать полный перебор?
Подскажите, можно реализовать полный перебор комбинаций символов? Понятно, что for (int i = 0; i...

Граф-схема микропрограммы
Помогите выполнить задание! Надеюсь на любую помощь! :-13 раз Время выполнения оператора в...

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru