Форум программистов, компьютерный форум 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 В данной задаче массив не нужен. Достаточно хранить текущее и предыдущее значения x и обновлять их после каждой итерации.
C++ Возможно ли написать свой класс 2д графики? http://www.cyberforum.ru/cpp-beginners/thread823399.html
Возможно ли написать свой класс 2д графики? Скажесм, который будет хронить х, у pixel-я, цвет pixel-я, массив растов pixel-ов и т.д. Ну и само сабой вывод этого массива на монитор не используя методы ОПЕНГЕЛЫ и ДИРИКИСЫ всякие. Если это в плане реализации возможно то пожалуйста ответьте какие книги читать на зту тему. ПЛИЗ, очнь хочется разобраться самому для личного опыта. Низкий вам...
C++ создание класса в С++ , простейшее задание Помогите создать класс по условию... Тип «Вариант распыление» определить как перечисление (enum) со значениями полей «брус», «доска необрезной», «доска обрезная», «рельс». Тип «древесина» определить как класс, содержащий: - Закрытые поля с породой дерева в виде символьной строки произвольной длины и целого типа с влажностью и плотностью древесины; - Все функции реализовать в соответствии... подробнее

Показать сообщение отдельно
Rendy
Сообщений: n/a

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

31.03.2013, 02:46. Просмотров 2447. Ответов 2
Метки (Все метки)

Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф - связный и в графе отсутствуют циклы. Проверку на связность я осуществляю с помощью поиска в глубину. Вопрос заключается в том, как мне "написать" проверку на циклы? В просмотренной литературе ничего подходящего найти не могу, либо написано сложно для понимая: векторы и т.д. Надеюсь на помощь начинающему программисту.
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
 
void dfs(int v, int **Array, int n, int *Array1)
{
    Array1[v] = 1;
 
    for (int i = 0; i < n; i++)
    {
        if (Array[v][i] == 1 && Array1[i] == 0)
            dfs(i, Array, n, Array1);
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
 
    int n;
 
    cin >> n;
 
    int **Array = new int *[n];
 
    for (int i = 0; i < n; i++) 
        Array[i] = new int [n];
  
    int *Array1 = new int [n];
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> Array[i][j];
 
        Array1[i] = 0;
    }
 
    dfs(n - 1, Array, n, Array1);
 
    for (int i = 0; i < n; i++)
    {
        if (Array1[i] == 0)
        {
            cout << "NO" << endl;
 
            return 0;
        }
    }
 
    cout << "YES" << endl;
 
    return 0;
}
Если кому интересно - сама задача.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru