Форум программистов, компьютерный форум 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) со значениями полей «брус», «доска необрезной», «доска обрезная», «рельс». Тип «древесина»... подробнее

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

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

31.03.2013, 02:46. Просмотров 2643. Ответов 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