Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/25: Рейтинг темы: голосов - 25, средняя оценка - 4.60
5 / 54 / 21
Регистрация: 12.03.2017
Сообщений: 515
1

Дан неориентированный граф. Необходимо определить, является ли он деревом

16.12.2017, 19:47. Просмотров 4745. Ответов 1
Метки нет (Все метки)

Дан неориентированный граф. Необходимо определить, является ли он деревом.

Формат входных данных
В первой строке входного файла содержится одно натуральное число NN (1≤N≤1001≤N≤100) — количество вершин в графе. Далее в NN строках по NN чисел дана матрица смежности графа: в ii-ой строке на jj-ом месте стоит 1, если вершины ii и jj соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Формат выходных данных
Требуется вывести «YES», если граф является деревом, и «NO» иначе.
Примеры
входные данные
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
выходные данные
NO
входные данные
3
0 1 0
1 0 1
0 1 0
выходные данные
YES

Вот прога, которая не проходит несколько тестов:
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
#include <iostream>
#include <fstream>
 
int components(int N, int *edges, int M)
{
    int *rep = new int[N];
 
    for (int i = 0; i < N; ++i)
        rep[i] = i;
 
    for (int i = 0, p, q; i < 2 * M; i += 2)
    {
        for (p = edges[i]; p != rep[p]; p = rep[p]);
        for (q = edges[i + 1]; q != rep[q]; q = rep[q]);
 
        if (p == q) continue;
        rep[p] = q;
    }
 
    int cnt = 0;
 
    return cnt;
}
 
int main()
{
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");
 
    if (!ifs || !ofs)
        return 1;
 
    int N, M;
    int *edges;
    int cnt;
 
    ifs >> N >> M;
    edges = new int[2 * M];
 
    for (int i = 0; i < 2 * M; i += 2)
    {
        ifs >> edges[i] >> edges[i + 1];
        --edges[i];
        --edges[i + 1];
    }
 
    cnt = components(N, edges, M);
    std::cout << cnt << std::endl;
    ofs << cnt << std::endl;
    getchar();
    getchar();
    return 0;
}
Тесты, которые не проходят:
5
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
Вывод
NO
------------------------------------------------
10
0 0 1 1 0 0 1 0 0 1
0 0 1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 0 1 1
1 1 0 0 1 0 0 1 1 0
0 0 1 1 0 1 1 1 1 0
0 0 1 0 1 0 1 1 1 1
1 1 1 0 1 1 0 0 1 1
0 1 0 1 1 1 0 0 1 1
0 1 1 1 1 1 1 1 0 0
1 1 1 0 0 1 1 1 0 0
Вывод
NO
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.12.2017, 19:47
Ответы с готовыми решениями:

Является ли граф - деревом?
Доброго времени суток. Есть граф, нужно пробежаться по нему в ширину, и если не встретится циклов,...

Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является...

Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Дан ориентированный граф из n узлов и m рёбер. Проверить, является ли он деревом. Помогите...

Определить, является ли дерево AVL деревом
int s, kol, sr, a; void avl(PNode ptr) { int h1 = 0, h2 = 0, i = 0; if ((ptr-&gt;Left == NULL)...

1
277 / 226 / 93
Регистрация: 27.06.2016
Сообщений: 639
16.12.2017, 20:03 2
Pavlin234,
C++
1
ifs >> N >> M;
В условии задачи сказано, что перед матрицей вводится одно число, а не два.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.12.2017, 20:03

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Определить,является ли граф деревом
Помогите пожалуйста,завтра надо сдать работу... 1.Задано матрицу смежности простого...

Определить, является ли данный связный неориентированный граф двудольным
Метод решения: Поиск в глубину. Файл исходных данных: Граф, заданный списками смежностей. N...

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

Составить алгоритм, определяющий, является ли конечный неориентированный граф гамильтоновым (теорема Дирака)
Ребята помогите составить алгоритм пожалуйста, с помощью которого для любого конечного...


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

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

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