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

Определить число листьев на каждом уровне дерева - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Непонятки с конструктором копирования http://www.cyberforum.ru/cpp-beginners/thread1206840.html
class Table { Row* p; size_t size; public: Table(int i = 0) { p = new Row; size = i; }
C++ Техническое предложение к программе Как правильно оформлять техническое предложение для программы? Может у кого-нибудь есть пример оформления? Например: программа на C++, ООП, Студенческий отдел кадров. Добавлено через 9 часов 42 минуты Техническое задание уже написал, вот осталось написать техническое предложение http://www.cyberforum.ru/cpp-beginners/thread1206838.html
C++ Как организовать вывод двумерного массива (целые числа) из текстового файла?
Люди, объясните младшему товарищу. как организовать вывод двумерного массива(целые числа) из текстового файла. скрин прилагается. работаю на vs 2013.
Class Matrix. Используя перегрузку C++
Создать класс матрица Данный класс содержит указатель на long, размер строк и столбцов и состояние ошибки. Определить конструктор без параметров, конструктор с одним параметром и конструктор с двумя параметрами, деструктор. Конструктор без параметров выделяет место для одного элемента и инициализирует его в ноль. Конструктор с одним параметром, - размер массива, - выделяет место и...
C++ Создание библиотеки для работы со стеками http://www.cyberforum.ru/cpp-beginners/thread1206825.html
Есть задание "разработать библиотеку для работы со структурой данных типа стек" . Я создал 3 файла: первый "stek.cpp", в котором содержится функция main и вызов функций для работы со стеком: #include <iostream> #include <conio.h> #include <stdio.h> #include <stdlib.h> #include "iostek.h" using namespace std; int main();
C++ Создать стек на основе контейнера vector На основе контейнера vector построить стек целых чисел. Выполнить операции занесения элемента в стек, извлечение значения с вершины стека, вывода всех значений стека на экран, определения количества элементов стека. Предусмотреть возможности: - Формирование входных данных заданного размера (количество точек для проверки); - Сохранение входных данных в файле с заданной названием; -... подробнее

Показать сообщение отдельно
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
13.06.2014, 08:41     Определить число листьев на каждом уровне дерева
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#pragma comment(linker, "/STACK:167177216")
 
#include <stdio.h>
#include <stack>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <memory.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <time.h>
#include <cassert>
#include <cstring>
//#include <unordered_set>
 
using namespace std;
 
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define x first
#define y second
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
 
const int INF = 1e9;
const ld eps = 1e-9;
const li MOD = (li)(4e6 + 37);
const li INF64 = (li)(INF) * (li)(INF);
 
const int ddx[] = {-1, 1, 1, -1};
const int ddy[] = {1, 1, -1, -1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dxh[] = {-1, -1, -1, 1, 1, 1, 1, -1};
const int dyh[] = {1, -1, -1, -1, -1, 1, 1, 1};
const string dirs[] = {"RIGHT", "UP", "LEFT", "DOWN"};
 
const int N = 1000;
 
vector<int> g[N]; //spiski smezhnosti dereva
bool used[N]; //poseshali vershinu ili net
int depth[N]; //massiv glubin depth[i] == glubina vershini i
int max_deep = 0; // max glubina v dereve
int n; //kolichestvo vershin v dereve i kolichestvo reber
 
 
//poisk v glubinu: prinimaet vershinu i ee glubinu
void dfs(int v, int deep)
{
    used[v] = true;
    depth[v] = deep;
    max_deep = max(max_deep, deep);
    
    for(int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if(!used[to])
        {
            used[to] = true;
            dfs(to, deep + 1);
        }
    }
}
 
//sama funkciya
//type idet po vsem vershinam i esli glubina vershini ravna trebuemoy i vershina list(u nee tolko 1 rebro) to uvelichivaet otvet
 
int cnt(int deep)
{
    if(deep < 1 || deep > max_deep)
        return 0;
    if(deep == 1)
        return 0;
    
    int res = 0;
 
    for(int i = 1; i <= n; i++)
        if(depth[i] == deep && g[i].size() == 1)
            res++;
 
    return res;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //freopen("errors.txt", "w", stderr);
    //ios_base::sync_with_stdio(false);
    
 
    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
 
    //cout << "777" << endl;
 
    dfs(1, 1);
 
    //cout << "WTF" << endl;
 
    for(int i = 1; i <= max_deep; i++)
    {
        cout << "kolichestvo list'ev na glubine " << i << " == " << cnt(i) << endl;
    }
 
    return 0;
}
http://pastebin.com/Kaex3huQ

ну вообще непонятно как именно должна выглядесть функция, просто можно заранее все насчитать, а функция будет просто брать ответ и возращать его, но я там написал, чтобы функция все считала!
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru