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

Является ли граф деревом - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ массив структур http://www.cyberforum.ru/cpp-beginners/thread823425.html
Написать функцию для создания массива записей со сведениями о студентах (ФИО, возраст, курс, успеваемость). По заданному массиву определить средний бал успеваемости студентов n курса.
C++ Текстовые и бинарные файлы. Получить файл g из чисел исходного файла Компоненты файла f – целые числа, положительных чисел столько же, сколько отрицательных. Получить файл g из чисел исходного файла, в ко-тором не было бы двух соседних чисел с одинаковым знаком. http://www.cyberforum.ru/cpp-beginners/thread823423.html
Как преобразовать long double в char[]? C++
Приветствую. Подскажите пожалуйста, как преобразовать long double в в тип char? До указателей по книге еще не дошел, в интернете пытался найти функцию, так и не разобрался. Самое интересное что в...
C++ написать прогу для извлечения корня метод касательных
Напишите подпрограмму вычисления квадратного корня с использованием метода касательных (Ньютона): x(0) = a 1 a x(n+1) = - * ( ---- + x(n)) 2 x(n) Итерировать, пока не будет | x(n+1) - x(n) | < 0.001...
C++ Возможно ли написать свой класс 2д графики? http://www.cyberforum.ru/cpp-beginners/thread823399.html
Возможно ли написать свой класс 2д графики? Скажесм, который будет хронить х, у pixel-я, цвет pixel-я, массив растов pixel-ов и т.д. Ну и само сабой вывод этого массива на монитор не используя методы...
C++ создание класса в С++ , простейшее задание Помогите создать класс по условию... Тип «Вариант распыление» определить как перечисление (enum) со значениями полей «брус», «доска необрезной», «доска обрезная», «рельс». Тип «древесина»... подробнее

Показать сообщение отдельно
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
31.03.2013, 19:29
если у графа н-1 ребро и при этом он связен, то граф - дерево. Проверку на связность напишите сами?

Добавлено через 2 минуты
может быть не очевидно - если он связен и ребер ровно н-1, то циклов быть не может...

Добавлено через 19 минут
чуть позже прикреплю код проверки на циклы.

Добавлено через 6 часов 8 минут
C++
1
2
3
4
5
6
7
8
9
int color[N];
 
void dfs(int v) {
color[v] = 1;
for(int i=0; i < N; i++)
if(g[v][i] != -1 && color[i] == 1)
cycle_find = true;
color[v] = 2;
}
не умею я писать абстрактно... в общем, в чем дело: для каждой вершины мы храним так называемый "цвет". 0 - вершина не посещена до сих пор, 1 - дфс зашел в эту вершину, но еще не вышел, 2 - дфс вышел из вершины. таким образом, если мы идем в вершину с цветом 1, то мы идем в вершину, из которой еще не вышли, то есть образуем цикл.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru