Форум программистов, компьютерный форум, киберфорум
Наши страницы

таблица знакомств - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевод кода из Паскаля на C++ http://www.cyberforum.ru/cpp-beginners/thread194101.html
обясните несколько строчек из паскаля, или перевидите их в с++ j1,er числа, i1 char вроде строки val(i1,j1,er); writeln(''); readln; write(i,' ');
C++ Наследование Тёмного времени суток! Столкнулся с проблемой, основной смысл которой заложен ниже class Parent { void F() = 0; } class Child: protected Parent { void F() {} http://www.cyberforum.ru/cpp-beginners/thread194096.html
Цикл сортировки. C++
Доброго времени суток. Такая вот у меня проблема. Предположим у меня есть два массива: {1, 2, 2, 1, 3, 3, 2, 1, 0, 0} {1, 0, 1, 2, 0, 1, 2, 3, 2, 3} как мне их упорядочить чтобы получить в итоге:...
C++ Сортировка массива [C++]
Доброго времени суток, уважаемые. Не получается сделать сортировку массива, а именно: необходимо сделать сортировку каждого из 3х столбцов в порядке убывания элементов. Метод сортировки неважен....
C++ Потоки вывода http://www.cyberforum.ru/cpp-beginners/thread194077.html
Даже не знаю как правильно сформулировать, но хотел сделать примерно следующее и вошел в ступор. Как создать класс, который смог бы привязаться к потокам cout/clog/cerr по выбору пользователя? То...
C++ Библиотека libzip Я так и не смог разобраться - можно ли с использованием данной библиотеки запаковывать в один архив файлы с разным сжатием? Нет ли ссылок на примеры кода использующего работу с атрибутами файлов?... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
20.11.2010, 11:16
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
//////////////////////////////////////////////////////////////////////////////////////
//Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], 
//в которой элемент A[i,j] равен 1, если человек i знаком с человеком j, 
//и, соответственно, наоборот, А[i,j]=А[j,i]. 
//Выяснить, можно ли разбить людей на 2 группы так, чтобы в каждой группе 
//были только незнакомые люди.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
enum T_color
{
    NO_COLOR = 0,
    WHITE,
    BLACK    
};
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                   T_vertice;
typedef std::set<T_vertice>           T_vertices_set;
typedef std::vector<T_vertice>        T_vertices;
typedef T_vertices_set                T_edge;
typedef std::set<T_edge>              T_edges;
typedef std::map<T_vertice, bool>     T_row;
typedef std::map<T_vertice, T_row>    T_matr;
typedef std::map<T_vertice, int>      T_vertice_time;
typedef std::map<T_vertice, T_color>  T_vert_color;
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr(T_matr&  matr, const T_vertices&  vertices)
{
    
    for(T_vertices::const_iterator  vertice_row_it = vertices.begin();
        vertice_row_it != vertices.end(); ++vertice_row_it)
    {
        for(T_vertices::const_iterator  vertice_col_it = vertices.begin();
            vertice_col_it != vertices.end(); ++vertice_col_it)
        {
            std::cout << '\t'
                      << matr[*vertice_row_it][*vertice_col_it];
                      
        } 
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }  
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_edges&  edges)
{
    T_vertices_set  vertices_set;
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++ edge_it)
    {
        vertices_set.insert(*edge_it->begin());
        vertices_set.insert(*edge_it->rbegin());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_matr  get_adjacency_matr(const T_edges&    edges)
{   
    T_matr  adjacency_matr;
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++ edge_it)
    {
        T_vertice  v1 = *edge_it->begin();
        T_vertice  v2 = *edge_it->rbegin();
        
        adjacency_matr[v1][v2] = adjacency_matr[v2][v1] = true;        
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_depth_first_black_white_colouring
    (
        T_vertice         vertice_U,
        T_color           color_prev,
        const T_vertices  vertices,                  
        T_matr&           adjacency_matr,
        T_vert_color&     vert_color,
        T_vertices&       vertices_white,
        T_vertices&       vertices_black
    )
{
    if(color_prev == WHITE)
    {
        vert_color[vertice_U] = BLACK;
        vertices_black.push_back(vertice_U);
    }
    else
    {
        vert_color[vertice_U] = WHITE;
        vertices_white.push_back(vertice_U);   
    }
    
    for(T_vertices::const_iterator  vertice_it_V = vertices.begin();
        vertice_it_V != vertices.end(); ++vertice_it_V)
    {
        if(adjacency_matr[vertice_U][*vertice_it_V])
        {
            if(vert_color[*vertice_it_V] == NO_COLOR)
            {
                if(
                      !successfully_depth_first_black_white_colouring
                         (
                             *vertice_it_V,
                             vert_color[vertice_U],
                             vertices,
                             adjacency_matr,
                             vert_color,
                             vertices_white,
                             vertices_black
                         )
                  )
                {
                    return false;
                }
            }
            else if(vert_color[vertice_U] == vert_color[*vertice_it_V])
            {
                return  false;
            }
        }
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_2_vertice_groups
    (
        const T_vertices  vertices,                  
        T_matr&           adjacency_matr
    )
{
    T_vertices  vertices_white;
    T_vertices  vertices_black;
    bool res_bool = true;
    
    T_vert_color  vert_color;
    for(T_vertices::const_iterator  vertice_it = vertices.begin();
        vertice_it != vertices.end(); ++vertice_it)
    {
        if(
              vert_color[*vertice_it] == NO_COLOR
              && !successfully_depth_first_black_white_colouring
                      (
                          *vertice_it,
                          BLACK,
                          vertices,
                          adjacency_matr,
                          vert_color,
                          vertices_white,
                          vertices_black
                      )
          )
        {
            res_bool = false;
            break;
        }
    }
    
    if(res_bool)
    {
        std::cout << "Граф является двудольным. Группы вершин:"
                  << std::endl
                  << "группа A:"
                  << std::endl
                  << "\t";
 
        std::copy(vertices_white.begin(), vertices_white.end(),
                  std::ostream_iterator<T_vertice>(std::cout, " "));
 
        std::cout << std::endl
                  << "группа B:"
                  << std::endl
                  << "\t";
 
        std::copy(vertices_black.begin(), vertices_black.end(),
                  std::ostream_iterator<T_vertice>(std::cout, " "));
    }
    else
    {
        std::cout << "Граф НЕ является двудольным.";
    }
    std::cout << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));   
    
    int n = 0;
    do
    {
        std::cout << "Введите количество ребер неориентированного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
 
    std::cout << "Введите ребра неориентированного графа "
                 "(вершины в ребре не должны совпадать):";
    T_edges  edges;
    
    do
    {
        std::cout << std::endl
                  << "ребро #"
                  << edges.size() + 1
                  << ":"
                  << std::endl
                  << "\t-> ";
        T_vertice  v1;
        std::cin >> v1;
        T_edge  edge_cur;
        edge_cur.insert(v1);
        
        T_vertice  v2;
        std::cout << "\t-> ";
        std::cin >> v2;        
        edge_cur.insert(v2);        
        if(edge_cur.size() == 2)
        {
            edges.insert(edge_cur);
        }        
    }while(static_cast<int>(edges.size()) < n);
 
    T_vertices  vertices = get_vertices(edges);
 
    T_matr  adjacency_matr = get_adjacency_matr(edges);
    std::cout << "Матрица смежности графа:"
              << std::endl;
 
    print_matr(adjacency_matr, vertices);
 
    print_2_vertice_groups(vertices, adjacency_matr);
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.