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

31.03.2013, 02:46. **Показов** 38664. **Ответов** 7

Студворк — интернет-сервис помощи студентам

Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф - связный и в графе отсутствуют циклы. Проверку на связность я осуществляю с помощью поиска в глубину. Вопрос заключается в том, как мне "написать" проверку на циклы? В просмотренной литературе ничего подходящего найти не могу, либо написано сложно для понимая: векторы и т.д. Надеюсь на помощь начинающему программисту.

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;
}

Если кому интересно - сама задача.

@soon · 31.03.2013, 04:26

Любое дерево с n вершинами содержит n-1 ребро.

@salam · 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, то мы идем в вершину, из которой еще не вышли, то есть образуем цикл.

@msz301005 · 29.05.2018, 16:28

Сообщение от salam

if(g[v][i] != -1 && color[i] == 1)

А тут точно g[v][i]!=-1 или тут g[v][i]!=0?

Добавлено через 21 минуту
salam, и в проверке графа на наличие цикла, то какое число надо кидать? n-1?

Добавлено через 1 час 3 минуты
Граф является деревом, если граф связный и в графе n-1 ребро. если эти два условия выполняются, то в графе нету циклов. Проверку на связность ты написал. Но этого недостаточно, тебе надо проверить, что в графе n-1 ребро. Это очень просто.

C++
1
2
3
4
5
6
7
8
int rebro=0;
for(int i = 0;i<n;i++){
    for(int j = 0;j<n;j++){
        cin>>Array[i][j];
        rebro+=Array[i][j];
    }
}
rebro/=2;

И потом к конце твоей программы на 51 строчке кода выводи не просто YES, а проверяй, если rebro==n-1, то выводи YES, иначе NO. Это можно сделать в одну строчку:

C++
1
cout<<(rebro==n-1?"YES":"NO");

@sadfasfsad · 09.01.2021, 17:52

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
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int g[1000][1000];
bool visited[1000];
 
void dfs(int v) {
    if (visited[v])
        return;
    visited[v] = true;
    for (int i = 0; i < n; i++)
        if (g[v][i])
            dfs(i);
}
 
int main() {
    int m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
 
 
    dfs(0);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            cout << "NO";
            return 0;
        }
    }
 
    bool b = true;
    bool e = (m - n + 1) == 0;
 
    cout << (b && e ? "YES" : "NO") << "\n";
 
    return 0;
}

@VyacheslavSqrt · 13.07.2021, 10:52

Похожая задача.
Неориентированный граф без петель и кратных ребер задан матрицей смежности. Требуется определить, является ли этот граф деревом.

Входные данные
Во входном файле INPUT.TXT записано сначала число N - количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N×N, в которой 1 обозначает наличие ребра, 0 - его отсутствие. Матрица симметрична относительно главной диагонали.

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
#include <bits/stdc++.h>
using namespace std;
int w[105][105], visited[105], n;
 
void dfs(int j) {
    visited[j] = 1;
    for (int i = 0; i < n; i++) {
        if (w[i][j] && !visited[i]) dfs(i);
    }
}
 
int main() {
    cin >> n;
    int k = 0, ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
            if (w[i][j]) k++;
        }
    }
    dfs(0);
    for (int i = 0; i < n; i++) {
        if (!visited[i])  ans = 0;
    }
 
    cout << ((ans && k / 2 == n - 1) ? "YES" : "NO");
    return 0;
}

Code
1
2
3
4
5
6
7
8
9
10
11
1   Accepted    0,015   328 Кб
2   Accepted    0,015   328 Кб
3   Accepted    0,015   332 Кб
4   Accepted    0,015   344 Кб
5   Accepted    0,015   340 Кб
6   Accepted    0,015   344 Кб
7   Accepted    0,015   336 Кб
8   Accepted    0,015   328 Кб
9   Accepted    0,015   332 Кб
10  Accepted    0,03            332 Кб
11  Accepted    0,015   340 Кб

Тест:
3
0 1 0
1 0 1
0 1 0
Ответ:
YES

@Kuzia domovenok · 13.07.2021, 12:06

VyacheslavSqrt, это был вопрос или ответ?

@llofrud · 01.12.2022, 23:53

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
int n,count=0,sum=0;
ifstream f ("graf_last.txt");
f>>n;
int **a = new int *[n];
for(int i=0; i<n; i++)
a[i]=new int [n];
while(!f.eof())
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
f>>a[i][j];
}
f.close();
for(int i=0; i<n; i++)
{
sum=0;
for(int j=0; j<n; j++)
if(a[i][j]==1)
{
sum++;
count++;
}
if(sum==0)
{
cout<<"graf ne derevo";
return 0;
}
}
if(sum/2==n-1) cout<<"graf - derevo";
else cout<<"graf ne derevo";
}

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	31.03.2013, 04:26
	Сообщение было отмечено Catstail как решение Решение Любое дерево с n вершинами содержит n-1 ребро. 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,536 Записей в блоге: 1
	13.07.2021, 12:06
	VyacheslavSqrt, это был вопрос или ответ? 0

@llofrud 0 / 0 / 0 Регистрация: 01.12.2022 Сообщений: 1
	01.12.2022, 23:53
	#include <iostream> #include <fstream> using namespace std; int main() { int n,count=0,sum=0; ifstream f ("graf_last.txt"); f>>n; int *a = new int [n]; for(int i=0; i<n; i++) a[i]=new int [n]; while(!f.eof()) { for(int i=0; i<n; i++) for(int j=0; j<n; j++) f>>a[i][j]; } f.close(); for(int i=0; i<n; i++) { sum=0; for(int j=0; j<n; j++) if(a[i][j]==1) { sum++; count++; } if(sum==0) { cout<<"graf ne derevo"; return 0; } } if(sum/2==n-1) cout<<"graf - derevo"; else cout<<"graf ne derevo"; } 0

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

Решение