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

не компилируется задание: компонент связности графа - кто разберется - C++

Восстановить пароль Регистрация
 
URFIN83
0 / 0 / 0
Регистрация: 25.06.2012
Сообщений: 18
03.09.2012, 19:26     не компилируется задание: компонент связности графа - кто разберется #1
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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
#include <iostream>
#include <conio.h>
#include <stdlib.h>
 
class Stack {
    private:
        int stackSize;
        int* stackArray;
        int counterOfStackElements;
    public:
        Stack(int n=1) : counterOfStackElements(0)
        {
            stackArray = new int[n+1];
            stackSize = n;
            *stackArray = 0;
        }
        ~Stack()
        {
            stackArray-=counterOfStackElements;
            delete[] stackArray;
        }
        void putElement(int element)
        {
            if(counterOfStackElements==stackSize) {
                std::cerr << "\n‘внЄ Ї®«®*!\n"; //Стэк полон!
                exit(1);
            }
            *++stackArray=element;
            counterOfStackElements++;
        }
        int getElement()
        {
            if(!counterOfStackElements)
                return 0;
            counterOfStackElements--;
            return *stackArray--;
        }
};
 
int main()
{
    char ch;
    while(true) {
        system("cls");
        std::cout << "1. ‚ў®¤ ¤***ле\n" //Ввод данных
                  << "2. ‚л室\n"; //Выход
        ch = _getch();
        if(ch=='2')
            return 0;
        if(ch!='1')
            continue;
        break;
    }
 
    while(true) {
        system("cls");
        int numOfPeaks;
        std::cout << "‚ўҐ¤ЁвҐ зЁб«® ўҐаиЁ* Ја*д*: "; //Введите число вершин графа
        std::cin >> numOfPeaks;
        if(!std::cin.good()) {
            std::cin.clear();
            //Число вершин задается цифрой. Попробуйте еще раз.
            std::cout << "—Ёб«® ўҐаиЁ* §*¤*Ґвбп жЁда®©. Џ®Їа®Ўг©вҐ ҐйҐ а*§.\n\n\n";
            //Нажмите любую клавишу для продолжения...
            std::cout << "Ќ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
            _getch();
            std::cin.ignore(30, '\n');
            continue;
        }
        if(!numOfPeaks) {
            std::cout << "—Ёб«® ўҐаиЁ* ¤®«¦*® Ўлвм Ў®«миҐ *г«п."; //Число вершин должно быть больше нуля
            //Нажмите любую клавишу для продолжения...
            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
            _getch();
            continue;
        }
        if(numOfPeaks<0) {
            //Число вершин не может быть отрицательным
            std::cout << "—Ёб«® ўҐаиЁ* *Ґ ¬®¦Ґв Ўлвм ®ваЁж*⥫м*л¬.";
            //Нажмите любую клавишу для продолжения...
            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
            _getch();
            continue;
        }
        if(numOfPeaks>26) {
            //Число вершин не должно быть больше 26
            std::cout << "—Ёб«® ўҐаиЁ* *Ґ ¤®«¦*® Ўлвм Ў®«миҐ 26.";
            //Нажмите любую клавишу для продолжения...
            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
            _getch();
            continue;
        }
        bool** matrix = new bool*[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            matrix[i] = new bool[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            for(int j=0; j<numOfPeaks; j++)
                matrix[i][j]=0;
 
        char* A = new char[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            A[i] = static_cast<char>(i+97);
 
        while(true) {
            system("cls");
            std::cout << "‡*¤*©вҐ ¬*ваЁжг ᬥ¦*®бвЁ:\n\n  "; //Задайте матрицу смежности
            for(int i=0; i<numOfPeaks; i++)
                std::cout << A[i] << ' ';
            for(int i=0; i<numOfPeaks; i++) {
                std::cout << '\n' << A[i] << ' ';
                for(int j=0; j<numOfPeaks; j++)
                    std::cout << matrix[i][j] << ' ';
            }
            //Введите пару элементов для изменения (клавиша ESC - завершить изменения):
            std::cout << "\n\n\n‚ўҐ¤ЁвҐ Ї*аг н«Ґ¬Ґ*в®ў ¤«п Ё§¬Ґ*Ґ*Ёп (Є«*ўЁи* ESC - §*ўҐаиЁвм Ё§¬Ґ*Ґ*Ёп): ";
            ch = _getch();
            if(static_cast<int>(ch)==27) {
                std::cout << "ESC\n";
                break;
            }
            if(ch<'a'||ch>'z') {
                //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                //Нажмите любую клавишу для продолжения...
                std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                _getch();
                continue;
            }
            int m=-1, n=-1;
            for(int i=0; i<numOfPeaks; i++)
                if(A[i]==ch) {
                    m = i;
                    break;
                }
            if(m<0) {
                //Вершины не существует
                std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.\n\n";
                //Нажмите любую клавишу для продолжения...
                std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                _getch();
                continue;
            }
            std::cout << '(' << ch << ',';
 
            ch = _getch();
            if(ch<'a'||ch>'z') {
                //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                //Нажмите любую клавишу для продолжения...
                std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                _getch();
                continue;
            }
            for(int i=0; i<numOfPeaks; i++)
                if(A[i]==ch) {
                    n = i;
                    break;
                }
            if(n<0) {
                //Вершины не существует
                std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.\n\n";
                //Нажмите любую клавишу для продолжения...
                std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                _getch();
                continue;
            }
            std::cout << ch << ")\n";
            if(matrix[m][n])
                matrix[m][n] = false;
            else
                matrix[m][n] = true;
        }
 
        while(true) {
            system("cls");
            std::cout << "Њ*ваЁж* ᬥ¦*®бвЁ:\n\n  "; //Матрица смежности
            for(int i=0; i<numOfPeaks; i++)
                std::cout << A[i] << ' ';
            for(int i=0; i<numOfPeaks; i++) {
                std::cout << '\n' << A[i] << ' ';
                for(int j=0; j<numOfPeaks; j++)
                    std::cout << matrix[i][j] << ' ';
            }
 
            std::cout << "\n\n\n\n‚лЎҐаЁвҐ ¤Ґ©бвўЁҐ:\n" //Выбирите действие
                      << "1. ђҐ¤*ЄвЁа®ў*вм ¬*ваЁжг\n" //Редактировать матрицу
                      << "2. €§¬Ґ*Ёвм зЁб«® ўҐаиЁ*\n" //Изменить число вершин
                      << "3. ЋЇаҐ¤Ґ«Ёвм Є®¬Ї®*Ґ*вл бўп§*®бвЁ\n" //Определить компоненты связности
                      << "4. ЋЇаҐ¤Ґ«Ёвм Є®¬Ї®*Ґ*вл бЁ«м*®© бўп§*®бвЁ\n" //Определить компоненты сильной связности
                      << "5. ‚л©вЁ Ё§ Їа®Ја*¬¬л\n"; //Выйти из программы
            ch = _getch();
            switch(ch) {
                case '1':
                    while(true) {
                        system("cls");
                        std::cout << "‡*¤*©вҐ ¬*ваЁжг ᬥ¦*®бвЁ:\n\n  "; //Задайте матрицу смежности
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        for(int i=0; i<numOfPeaks; i++) {
                            std::cout << '\n' << A[i] << ' ';
                            for(int j=0; j<numOfPeaks; j++)
                                std::cout << matrix[i][j] << ' ';
                        }
                        //Введите пару элементов для изменения (клавиша ESC - завершить изменения):
                        std::cout << "\n\n\n‚ўҐ¤ЁвҐ Ї*аг н«Ґ¬Ґ*в®ў ¤«п Ё§¬Ґ*Ґ*Ёп (Є«*ўЁи* ESC - §*ўҐаиЁвм Ё§¬Ґ*Ґ*Ёп): ";
                        ch = _getch();
                        if(static_cast<int>(ch)==27) {
                            std::cout << "ESC\n";
                            break;
                        }
                        if(ch<'a'||ch>'z') {
                            //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                            std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        int m=-1, n=-1;
                        for(int i=0; i<numOfPeaks; i++)
                            if(A[i]==ch) {
                                m = i;
                                break;
                            }
                        if(m<0) {
                            //Вершины не существует
                            std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        std::cout << '(' << ch << ',';
 
                        ch = _getch();
                        if(ch<'a'||ch>'z') {
                            //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                            std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        for(int i=0; i<numOfPeaks; i++)
                            if(A[i]==ch) {
                                n = i;
                                break;
                            }
                        if(n<0) {
                            //Вершины не существует
                            std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        std::cout << ch << ")\n";
                        if(matrix[m][n])
                            matrix[m][n] = false;
                        else
                            matrix[m][n] = true;
                    }
                    continue;
                case '2':
                    break;
                case '3':
                    while(true) {
                        system("cls");
                        std::cout << "‚лЎҐаЁвҐ **з*«м*го ўҐаиЁ*г: "; //Выберите начальную вершину
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        std::cout << std::endl;
                        ch = _getch();
                        if(ch>static_cast<char>(numOfPeaks+96)) {
                            //Вершины не существует
                            std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        else if(ch<'a'||ch>'z') {
                            //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                            std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        break;
                    }
                    system("cls");
                    std::cout << "Ќ*з*«м**п ўҐаиЁ**: " << ch; //Начальная вершина
                    std::cout << "\n\nЏ®б«Ґ¤®ў*⥫м*®бвм ўҐаиЁ*:\n"; //Последовательность вершин
                    {
                    bool* marks = new bool[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        marks[i] = false;
                    Stack* st = new Stack(numOfPeaks);
                    int component = 1;
                    st->putElement(static_cast<int>(ch-96));
                    marks[static_cast<int>(ch-97)] = true;
                    while(true) {
                        int peak = st->getElement();
                        if(!peak)
                            break;
                        for(int i=0; i<numOfPeaks; i++)
                            if(matrix[peak-1][i])
                                if(!marks[i]) {
                                    st->putElement(i+1);
                                    marks[i] = true;
                                }
                        std::cout << static_cast<char>(peak+96) << ' ';
                    }
                    std::cout << std::endl;
                    for(int i=0; i<numOfPeaks; i++)
                        if(!marks[i]) {
                            component++;
                            st->putElement(i+1);
                            marks[i] = true;
                            while(true) {
                                int peak = st->getElement();
                                if(!peak)
                                    break;
                                for(int i=0; i<numOfPeaks; i++)
                                    if(matrix[peak-1][i])
                                        if(!marks[i]) {
                                            st->putElement(i+1);
                                            marks[i] = true;
                                        }
                                std::cout << static_cast<char>(peak+96) << ' ';
                            }
                            std::cout << std::endl;
                        }
                    //Количество компонент связности
                    std::cout << "\nЉ®«ЁзҐбвў® Є®¬Ї®*Ґ*в бўп§*®бвЁ = " << component;
                    //Нажмите любую клавишу для продолжения...
                    std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                    _getch();
                    delete st;
                    delete[] marks;
                    }
                    continue;
                case '4':
                    system("cls");
                    {
                    bool** accessibility = new bool*[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        accessibility[i] = new bool[numOfPeaks];
 
                    for(int i=0; i<numOfPeaks; i++)
                        for(int j=0; j<numOfPeaks; j++)
                            accessibility[i][j] = matrix[i][j];
                    //Алгоритм Флойда — Уоршелла
                    for(int k=0; k<numOfPeaks; k++)
                        for(int i=0; i<numOfPeaks; i++)
                            for(int j=0; j<numOfPeaks; j++)
                                accessibility[i][j] = accessibility[i][j]||(accessibility[i][k]&&accessibility[k][j]);
 
                    bool** disoriented = new bool*[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        disoriented[i] = new bool[numOfPeaks];
 
                    for(int i=0; i<numOfPeaks; i++)
                        for(int j=0; j<numOfPeaks; j++)
                            disoriented[i][j] = false;
 
                    for(int k=0; k<numOfPeaks; k++)
                        for(int i=0; i<numOfPeaks; i++) {
                            if(i==k)
                                continue;
                            bool is_equal = true;
                            bool is_zero = true;
                            for(int j=0; j<numOfPeaks; j++) {
                                if(is_zero) {
                                    if(accessibility[i][j]==true)
                                        is_zero = false;
                                }
                                if(accessibility[k][j]!=accessibility[i][j]) {
                                    is_equal = false;
                                    break;
                                }
                            }
                            if(is_zero)
                                continue;
                            if(is_equal)
                                disoriented[k][i] = true;
                        }
 
                    while(true) {
                        system("cls");
                        std::cout << "‚лЎҐаЁвҐ **з*«м*го ўҐаиЁ*г: "; //Выберите начальную вершину
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        std::cout << std::endl;
                        ch = _getch();
                        if(ch>static_cast<char>(numOfPeaks+96)) {
                            //Вершины не существует
                            std::cout << "\n‚ҐаиЁ*л \'" << ch << "\' *Ґ бгйҐбвўгҐв.";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        else if(ch<'a'||ch>'z') {
                            //Неверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').
                            std::cout << "\nЌҐўҐа*л© бЁ¬ў®«. ‚ў®¤ЁвҐ в®«мЄ® бва®з*лҐ ЎгЄўл «*вЁ*бЄ®Ј® *«д*ўЁв* (®в 'a' ¤® 'z').\n\n";
                            //Нажмите любую клавишу для продолжения...
                            std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                            _getch();
                            continue;
                        }
                        break;
                    }
                    system("cls");
                    std::cout << "Ќ*з*«м**п ўҐаиЁ**: " << ch; //Начальная вершина
                    std::cout << "\n\nЏ®б«Ґ¤®ў*⥫м*®бвм ўҐаиЁ*:\n"; //Последовательность вершин
                    bool* marks = new bool[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        marks[i] = false;
                    Stack* st = new Stack(numOfPeaks);
                    int component = 1;
                    st->putElement(static_cast<int>(ch-96));
                    marks[static_cast<int>(ch-97)] = true;
                    while(true) {
                        int peak = st->getElement();
                        if(!peak)
                            break;
                        for(int i=0; i<numOfPeaks; i++)
                            if(disoriented[peak-1][i])
                                if(!marks[i]) {
                                    st->putElement(i+1);
                                    marks[i] = true;
                                }
                        std::cout << static_cast<char>(peak+96) << ' ';
                    }
                    std::cout << std::endl;
                    for(int i=0; i<numOfPeaks; i++)
                        if(!marks[i]) {
                            component++;
                            st->putElement(i+1);
                            marks[i] = true;
                            while(true) {
                                int peak = st->getElement();
                                if(!peak)
                                    break;
                                for(int i=0; i<numOfPeaks; i++)
                                    if(disoriented[peak-1][i])
                                        if(!marks[i]) {
                                            st->putElement(i+1);
                                            marks[i] = true;
                                        }
                                std::cout << static_cast<char>(peak+96) << ' ';
                            }
                            std::cout << std::endl;
                        }
                    //Количество компонент связности
                    std::cout << "\nЉ®«ЁзҐбвў® Є®¬Ї®*Ґ*в бЁ«м*®© бўп§*®бвЁ = " << component;
                    //Нажмите любую клавишу для продолжения...
                    std::cout << "\n\n\nЌ*¦¬ЁвҐ «оЎго Є«*ўЁиг ¤«п Їа®¤®«¦Ґ*Ёп...";
                    _getch();
 
                    delete st;
                    delete[] marks;
 
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] disoriented[i];
                    delete[] disoriented;
 
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] accessibility[i];
                    delete[] accessibility;
                    }
                    continue;
                case '5':
                    delete[] A;
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] matrix[i];
                    delete[] matrix;
                    return 0;
                default:
                    continue;
            }
            break;
        }
 
        delete[] A;
        for(int i=0; i<numOfPeaks; i++)
            delete[] matrix[i];
        delete[] matrix;
    }
    return 0;
}
Добавлено через 21 минуту
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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
#include <iostream>
#include <conio.h>
#include <stdlib.h>
 
/*В работе программы будет использован поиск в глубину. Для этого создадим некое подобие стэка.*/
class Stack {
    private:
        int stackSize;
        int* stackArray;
        int counterOfStackElements;
    public:
        /*В конструкторе реализуем массив на нужное нам число элементов*/
        Stack(int n=1) : counterOfStackElements(0)
        {
            stackArray = new int[n+1];
            stackSize = n;
            *stackArray = 0;
        }
        /*В деструкторе, дабы не допустить утечек, память освободим*/
        ~Stack()
        {
            stackArray-=counterOfStackElements;
            delete[] stackArray;
        }
        void putElement(int element)
        {
            /*Переполнить стэк в этой программе вряд ли удастся, но на всякий случай создадим простейшую защиту*/
            if(counterOfStackElements==stackSize) {
                std::cerr << "\nСтэк полон!\n";
                exit(1);
            }
            *++stackArray=element;
            counterOfStackElements++;
        }
        int getElement()
        {
            /*Поскольку реализация стэка довольно проста, то в одном из циклов программы возможен выход «в минус», т.е. за 
            пределы выделенной памяти. Чтобы этого не произошло, при достижении переменной counterOfStackElements нуля 
            метод будет возвращать ноль*/
            if(!counterOfStackElements)
                return 0;
            counterOfStackElements--;
            return *stackArray--;
        }
};
 
int main()
{
    char ch;
    while(true) {
        system("cls");
        std::cout << "1. Ввод данных\n"
                       << "2. Выход\n";
        ch = _getch();
        if(ch=='2')
            return 0;
        if(ch!='1')
            continue;
        break;
    }
 
    while(true) {
        system("cls");
        int numOfPeaks;
        std::cout << "Введите число вершин графа: ";
        std::cin >> numOfPeaks;
        /*Не даем ввести что-либо кроме цифр*/
        if(!std::cin.good()) {
            std::cin.clear();
            std::cout << "Число вершин задается цифрой. Попробуйте еще раз.\n\n\n";
            std::cout << "Нажмите любую клавишу для продолжения...";
            _getch();
            std::cin.ignore(30, '\n');
            continue;
        }
        /*Не даем ввести ноль*/
        if(!numOfPeaks) {
            std::cout << "Число вершин должно быть больше нуля.";
            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
            _getch();
            continue;
        }
        /*Не даем ввести отрицательное число (в принципе, можно было бы объединить с предыдущим условием)*/
        if(numOfPeaks<0) {
            std::cout << "Число вершин не может быть отрицательным.";
            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
            _getch();
            continue;
        }
        /*Поскольку за обозначения вершин я принял строчные буквы латинского алфавита, то число вершин ограничим 26-ю*/
        if(numOfPeaks>26) {
            std::cout << "Число вершин не должно быть больше 26.";
            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
            _getch();
            continue;
        }
        /*Создадаем матрицу смежности*/
        bool** matrix = new bool*[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            matrix[i] = new bool[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            for(int j=0; j<numOfPeaks; j++)
                matrix[i][j]=0;
 
        char* A = new char[numOfPeaks];
        for(int i=0; i<numOfPeaks; i++)
            A[i] = static_cast<char>(i+97);
 
        /*Вводим все необходимые данные*/
        while(true) {
            system("cls");
            std::cout << "Задайте матрицу смежности:\n\n  ";
            for(int i=0; i<numOfPeaks; i++)
                std::cout << A[i] << ' ';
            for(int i=0; i<numOfPeaks; i++) {
                std::cout << '\n' << A[i] << ' ';
                for(int j=0; j<numOfPeaks; j++)
                    std::cout << matrix[i][j] << ' ';
            }
            std::cout << "\n\n\nВведите пару элементов для изменения (клавиша ESC - завершить изменения): ";
            ch = _getch();
            if(static_cast<int>(ch)==27) {
                std::cout << "ESC\n";
                break;
            }
            if(ch<'a'||ch>'z') {
                std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                _getch();
                continue;
            }
            int m=-1, n=-1;
            for(int i=0; i<numOfPeaks; i++)
                if(A[i]==ch) {
                    m = i;
                    break;
                }
            if(m<0) {
                std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                _getch();
                continue;
            }
            std::cout << '(' << ch << ',';
 
            ch = _getch();
            if(ch<'a'||ch>'z') {
                std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                _getch();
                continue;
            }
            for(int i=0; i<numOfPeaks; i++)
                if(A[i]==ch) {
                    n = i;
                    break;
                }
            if(n<0) {
                std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                _getch();
                continue;
            }
            std::cout << ch << ")\n";
            if(matrix[m][n])
                matrix[m][n] = false;
            else
                matrix[m][n] = true;
        }
 
        /*Выводим на экран исходные данные и меню с выбором операций*/
        while(true) {
            system("cls");
            std::cout << "Матрица смежности:\n\n  ";
            for(int i=0; i<numOfPeaks; i++)
                std::cout << A[i] << ' ';
            for(int i=0; i<numOfPeaks; i++) {
                std::cout << '\n' << A[i] << ' ';
                for(int j=0; j<numOfPeaks; j++)
                    std::cout << matrix[i][j] << ' ';
            }
 
            std::cout << "\n\n\n\nВыбирите действие:\n"
                      << "1. Редактировать матрицу\n"
                      << "2. Изменить число вершин\n"
                      << "3. Определить компоненты связности\n"
                      << "4. Определить компоненты сильной связности\n"
                      << "5. Выйти из программы\n";
            ch = _getch();
            switch(ch) {
                /*Редактируем матрицу (изменяем граф)*/
                case '1':
                    while(true) {
                        system("cls");
                        std::cout << "Задайте матрицу смежности:\n\n  ";
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        for(int i=0; i<numOfPeaks; i++) {
                            std::cout << '\n' << A[i] << ' ';
                            for(int j=0; j<numOfPeaks; j++)
                                std::cout << matrix[i][j] << ' ';
                        }
                        std::cout << "\n\n\nВведите пару элементов для изменения (клавиша ESC - завершить изменения): ";
                        ch = _getch();
                        if(static_cast<int>(ch)==27) {
                            std::cout << "ESC\n";
                            break;
                        }
                        if(ch<'a'||ch>'z') {
                            std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        int m=-1, n=-1;
                        for(int i=0; i<numOfPeaks; i++)
                            if(A[i]==ch) {
                                m = i;
                                break;
                            }
                        if(m<0) {
                            std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        std::cout << '(' << ch << ',';
 
                        ch = _getch();
                        if(ch<'a'||ch>'z') {
                            std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        for(int i=0; i<numOfPeaks; i++)
                            if(A[i]==ch) {
                                n = i;
                                break;
                            }
                        if(n<0) {
                            std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        std::cout << ch << ")\n";
                        if(matrix[m][n])
                            matrix[m][n] = false;
                        else
                            matrix[m][n] = true;
                    }
                    continue;
                /*Задаем новое число вершин графа (для этого всего лишь надо прервать текущий цикл)*/
                case '2':
                    break;
                /*Определяем компоненты связности графа. Будем производить поиск в глубину*/
                case '3':
                    while(true) {
                        system("cls");
                        std::cout << "Выберите начальную вершину ";
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        std::cout << std::endl;
                        ch = _getch();
                        if(ch>static_cast<char>(numOfPeaks+96)) {
                            std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        else if(ch<'a'||ch>'z') {
                            std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        break;
                    }
                    system("cls");
                    std::cout << "Начальная вершина: " << ch;
                    std::cout << "\n\nПоследовательность вершин\n";
                    {
                    bool* marks = new bool[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        marks[i] = false;
                    Stack* st = new Stack(numOfPeaks);
                    int component = 1;
                    st->putElement(static_cast<int>(ch-96));
                    marks[static_cast<int>(ch-97)] = true;
                    while(true) {
                        int peak = st->getElement();
                        if(!peak)
                            break;
                        for(int i=0; i<numOfPeaks; i++)
                            if(matrix[peak-1][i])
                                if(!marks[i]) {
                                    st->putElement(i+1);
                                    marks[i] = true;
                                }
                        std::cout << static_cast<char>(peak+96) << ' ';
                    }
                    std::cout << std::endl;
                    for(int i=0; i<numOfPeaks; i++)
                        if(!marks[i]) {
                            component++;
                            st->putElement(i+1);
                            marks[i] = true;
                            while(true) {
                                int peak = st->getElement();
                                if(!peak)
                                    break;
                                for(int i=0; i<numOfPeaks; i++)
                                    if(matrix[peak-1][i])
                                        if(!marks[i]) {
                                            st->putElement(i+1);
                                            marks[i] = true;
                                        }
                                std::cout << static_cast<char>(peak+96) << ' ';
                            }
                            std::cout << std::endl;
                        }
                    std::cout << "\nКоличество компонент связности = " << component;
                    std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                    _getch();
                    delete st;
                    delete[] marks;
                    }
                    continue;
                /*Определяем компоненты сильной связности орграфа*/
                case '4':
                    system("cls");
                    {
                    bool** accessibility = new bool*[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        accessibility[i] = new bool[numOfPeaks];
 
                    for(int i=0; i<numOfPeaks; i++)
                        for(int j=0; j<numOfPeaks; j++)
                            accessibility[i][j] = matrix[i][j];
                    /*При помощи алгоритма Флойда — Уоршелла найдем матрицу достижимости*/
                    for(int k=0; k<numOfPeaks; k++)
                        for(int i=0; i<numOfPeaks; i++)
                            for(int j=0; j<numOfPeaks; j++)
                                accessibility[i][j] = accessibility[i][j] || (accessibility[i][k] && accessibility[k][j]);
                    /*Затем определим неориентированный граф, поиск компонент связности в котором даст нам 
                    компоненты связности исходного орграфа*/
                    bool** disoriented = new bool*[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        disoriented[i] = new bool[numOfPeaks];
 
                    for(int i=0; i<numOfPeaks; i++)
                        for(int j=0; j<numOfPeaks; j++)
                            disoriented[i][j] = false;
 
                    for(int k=0; k<numOfPeaks; k++)
                        for(int i=0; i<numOfPeaks; i++) {
                            if(i==k)
                                continue;
                            bool is_equal = true;
                            bool is_zero = true;
                            for(int j=0; j<numOfPeaks; j++) {
                                if(is_zero) {
                                    if(accessibility[i][j]==true)
                                        is_zero = false;
                                }
                                if(accessibility[k][j]!=accessibility[i][j]) {
                                    is_equal = false;
                                    break;
                                }
                            }
                            if(is_zero)
                                continue;
                            if(is_equal)
                                disoriented[k][i] = true;
                        }
 
                    while(true) {
                        system("cls");
                        std::cout << "Выберите начальную вершину: ";
                        for(int i=0; i<numOfPeaks; i++)
                            std::cout << A[i] << ' ';
                        std::cout << std::endl;
                        ch = _getch();
                        if(ch>static_cast<char>(numOfPeaks+96)) {
                            std::cout << "\n Вершины \'" << ch << "\' не существует.\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        else if(ch<'a'||ch>'z') {
                            std::cout << "\nНеверный символ. Вводите только строчные буквы латинского алфавита (от 'a' до 'z').\n\n";
                            std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                            _getch();
                            continue;
                        }
                        break;
                    }
                    system("cls");
                    std::cout << "Начальная вершина: " << ch;
                    std::cout << "\n\nПоследовательность вершин:\n";
                    bool* marks = new bool[numOfPeaks];
                    for(int i=0; i<numOfPeaks; i++)
                        marks[i] = false;
                    Stack* st = new Stack(numOfPeaks);
                    int component = 1;
                    st->putElement(static_cast<int>(ch-96));
                    marks[static_cast<int>(ch-97)] = true;
                    while(true) {
                        int peak = st->getElement();
                        if(!peak)
                            break;
                        for(int i=0; i<numOfPeaks; i++)
                            if(disoriented[peak-1][i])
                                if(!marks[i]) {
                                    st->putElement(i+1);
                                    marks[i] = true;
                                }
                        std::cout << static_cast<char>(peak+96) << ' ';
                    }
                    std::cout << std::endl;
                    for(int i=0; i<numOfPeaks; i++)
                        if(!marks[i]) {
                            component++;
                            st->putElement(i+1);
                            marks[i] = true;
                            while(true) {
                                int peak = st->getElement();
                                if(!peak)
                                    break;
                                for(int i=0; i<numOfPeaks; i++)
                                    if(disoriented[peak-1][i])
                                        if(!marks[i]) {
                                            st->putElement(i+1);
                                            marks[i] = true;
                                        }
                                std::cout << static_cast<char>(peak+96) << ' ';
                            }
                            std::cout << std::endl;
                        }
                    std::cout << "\nКоличество компонент связности = " << component;
                    std::cout << "\n\n\nНажмите любую клавишу для продолжения...";
                    _getch();
 
                    delete st;
                    delete[] marks;
 
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] disoriented[i];
                    delete[] disoriented;
 
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] accessibility[i];
                    delete[] accessibility;
                    }
                    continue;
                /*Освобождаем память и выходим из программы*/
                case '5':
                    delete[] A;
                    for(int i=0; i<numOfPeaks; i++)
                        delete[] matrix[i];
                    delete[] matrix;
                    return 0;
                default:
                    continue;
            }
            break;
        }
 
        delete[] A;
        for(int i=0; i<numOfPeaks; i++)
            delete[] matrix[i];
        delete[] matrix;
    }
    return 0;
}
вот такой вид немного лучше но все равно не компилируется
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2012, 19:26     не компилируется задание: компонент связности графа - кто разберется
Посмотрите здесь:

C++ Задание. Помогите кто шарит
Кто сможет написать два задание C++
Компилируется в С++ bulder 6.0 но не компилируется в VS 2010 express C++
Нужно немного переделать программу нахождения компонент сильной связности в графе C++
C++ Методом обхода в глубину определить число компонент связности и цикломатическое число графа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
03.09.2012, 20:03     не компилируется задание: компонент связности графа - кто разберется #2
URFIN83, Еще не все экстрасенсы вернулись из отпуска
Ты бы рассказал, что говорит компилятор, чем он не доволен?
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
03.09.2012, 20:09     не компилируется задание: компонент связности графа - кто разберется #3
URFIN83, используй std::stack!
/*Дальнобойная телепатия может давать незначительную погрешность*/
URFIN83
0 / 0 / 0
Регистрация: 25.06.2012
Сообщений: 18
03.09.2012, 20:15  [ТС]     не компилируется задание: компонент связности графа - кто разберется #4
Цитата Сообщение от Байт Посмотреть сообщение
URFIN83, Еще не все экстрасенсы вернулись из отпуска
Ты бы рассказал, что говорит компилятор, чем он не доволен?
визуал студио - LINK : error LNK2001: неразрешенный внешний символ "_WinMainCRTStartup"

С++ /ВС вообще много на что ругается
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
04.09.2012, 00:00     не компилируется задание: компонент связности графа - кто разберется #5
Цитата Сообщение от URFIN83 Посмотреть сообщение
визуал студио - LINK : error LNK2001: неразрешенный внешний символ "_WinMainCRTStartup"
у вас проект видимо win32, студия не может найти функцию WinMain. Создайте проект консольного приложения и запустите!!!
Yandex
Объявления
04.09.2012, 00:00     не компилируется задание: компонент связности графа - кто разберется
Ответ Создать тему
Опции темы

Текущее время: 03:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru