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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
20.11.2010, 03:34     таблица знакомств #1
помогите написать программу

Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], в которой элемент A[i,j] равен 1, если человек i знаком с человеком j, и, соответственно, наоборот, А[i,j]=А[j,i]. Выяснить, можно ли разбить людей на 2 группы так, чтобы в каждой группе были только незнакомые люди.
Информация о знакомствах задается вводом, в первой строке которого находится число N<250, а в следующих N строках - таблица знакомств А (без пробелов)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2010, 03:34     таблица знакомств
Посмотрите здесь:

таблица значений C++
Таблица в C++ C++
Таблица лексем и таблица идентификаторов C++
C++ Таблица
C++ Таблица умножения
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 08:49     таблица знакомств #2
Вариант:
Для решения этой задачи потребуется int mas[N] - будем его использовать в качестве очереди, и int mas1[N] - для установки номера группы (всего групп две: 1 и 2). Изначально всем элементам mas1[i] делаем значения 0.
Заносим в очередь номер 0 (первого человека). mas1[0]=1.
Затем цикл while()
- берем из очереди очередной номер человека. Проходим по таблице знакомств в соответствующей строке. Если A[i][j]==1, то смотрим на mas1[j]. Если mas1[j]==0, то делаем mas1[j]=2 (если mas1[i]=1) или mas1[j]=1 (если mas1[i]=2) и заносим j в очередь. Если mas1[i]==2 и mas1[j]==2 или mas1[i]==1 и mas1[j]==1, то выходим из цикла (в этом случаем разбить на 2 группы нельзя).
Если очередь закончилась и мы досрочно не вышли из цикла, то разбить на 2 группы можно.

Добавлено через 6 минут
У меня алгоритм не совсем полный (если будут существовать две или более изолированные группы), то мы таким алгоритмом просмотрим только одну изолированную группу. Нужно добавить рассмотренный алгоритм для всех изолированных групп. Но это не так и сложно.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,695
20.11.2010, 11:16     таблица знакомств #3
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);
}
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
20.11.2010, 14:42  [ТС]     таблица знакомств #4
Спасибо Огромное)))
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
23.11.2010, 04:15  [ТС]     таблица знакомств #5
исправте ошибки плиз

вот код :

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
#include <iostream.h>
void main()
{
    int a[250][250];  //ГІГ*áëèöГ*
    int mas[250];  //ëþäè î÷åðåäü
    int m[250][250]=0;  // yjvth uhegs õç
    int i,j;
    m[0][0]=1;
    while(m[i][j])
        if (a[i][j]==1)
        { 
            if (m[j]==0)
            {
                m[j]=2;
            }
            if ((m[j]==1)||(m[i]==1))
            {
                if (m[i]==2)
                {
                mas[i]=j;
                }
                if (((m[i]==2)&&(m[j]==2))||((m[i]==1)&&(m[j]=1)))
                {
                    break;
                }
                cout<<"EROR"<<endl;
                
                return(0);
        }}
                cout<<"YES"<<endl;
}

вот ошибки:

c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(6) : error C2440: 'initializing' : cannot convert from 'const int' to 'int [250][250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(14) : error C2440: '=' : cannot convert from 'const int' to 'int [250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(18) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(18) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2440: '=' : cannot convert from 'const int' to 'int [250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(28) : error C2562: 'main' : 'void' function returning a value
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(2) : see declaration of 'main'
Error executing cl.exe.

- 16 error(s), 0 warning(s)
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.11.2010, 07:36     таблица знакомств #6
Цитата Сообщение от asotel Посмотреть сообщение
исправте ошибки плиз
А ты сообщения компилатора читать умеешь? А чем отличается указатель от обычной переменной, знаешь? Про возвращаемые значения функций читал?
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
24.11.2010, 00:01  [ТС]     таблица знакомств #7
я не всмысле ошибки помпилятора, а ошибки в моем коде, во втором сообшении мне написали алгоритм
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
24.11.2010, 05:39     таблица знакомств #8
asotel, а вы думаете, компилятор вам от балды 27 строчек ошибок нагенерил? Нет, компилятор генерирует осмысленные сообщения, которые зависят от ошибок в коде, а не в компиляторе. И сообщения компилятора нужны затем, чтобы помочь программисту исправить ошибки в коде самостоятельно, а не бежать сразу на форму, не вникнув в суть ошибок.
taras atavin
24.11.2010, 06:20
  #9

Не по теме:

Цитата Сообщение от asotel Посмотреть сообщение
так, чтобы в каждой группе были только незнакомые люди.
?Надеюсь, A[i][i]=1? Кстати, на сях нет понятия многомерного массива. Это на паскале многомерный массив есть синоним массива массивов, а на сях вместо синонимичности ограничились заменой всех многомерных массивов массивами массивов.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.11.2010, 22:41     таблица знакомств
Еще ссылки по теме:

C++ хеш таблица
C++ Хэш таблица
Таблица умножения C++

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

Или воспользуйтесь поиском по форуму:
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
24.11.2010, 22:41  [ТС]     таблица знакомств #10
Цитата Сообщение от silent_1991 Посмотреть сообщение
asotel, а вы думаете, компилятор вам от балды 27 строчек ошибок нагенерил? Нет, компилятор генерирует осмысленные сообщения, которые зависят от ошибок в коде, а не в компиляторе. И сообщения компилятора нужны затем, чтобы помочь программисту исправить ошибки в коде самостоятельно, а не бежать сразу на форму, не вникнув в суть ошибок.


пишу еще раз ошибки помпилятора я просто так выложил, мне нужно чтоб ктото сверил алгоритм из второго сообшения с моим кодом
Yandex
Объявления
24.11.2010, 22:41     таблица знакомств
Ответ Создать тему
Опции темы

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