Задача. Определить класс, объектами которого являются бинарные транзитивные отношения на множестве {0,1,2,…,n-1}. Конструктор строит наименьшее транзитивное отношение, содержащее заданный массив пар.
Решение
#include <conio.h>
#include <iostream.h>
// Структура, хранящая номера начальной и конечной вершин
struct pair
{
int dom, cod; // Номера элементов (на единицу больше)
};
// Класс бинарного транзитивного отношения
class trel
{
private:
int *p; // Матрица смежности a(i,j) = p[i*n+j]
int *c; // Вспомогательный массив для закраски точек
static int n; // Количество точек
public:
// Конструктор
trel(int n0 = 0, pair *pr = NULL);
void rec(int s);
void show(); // Вывод отношения на экран
trel operator+(trel t2); // Объединение
trel operator&(trel t2); // Пересечение
};
// Конструктор строит наименьшее транзитивное отношение,
// содержащее массив пар
trel::trel(int n0, pair *pr)
{
int k,s;
c = new int [n]; // Цвета
p = new int [n*n];
for(k = 0; k < n*n; k++) p[k] = 0;
for (k = 0; k < n0; k++)
if(pr[k].dom-1<n&&pr[k].cod-1<n&&pr[k].dom>0&&pr[k].cod>0)
p[ (pr[k].dom — 1) * n + pr[k].cod — 1 ] = 1;
// Доступные из p[i][j]=p[i*n+j]
for(s = 0; s < n; s++)
{
for(k = 0; k < n; k++) c[k] = 0;
//c[s] = 1; // если надо сделать рефлексивным
rec(s);
for(k = 0; k < n; k++) p[s*n+k] = c[k];
}
}
void trel::rec(int s)
{
int i;
for (i = 0; i < n; i++)
if(p[s * n + i] && !c[i])
{
c[i] = 1; rec(i);
}
}
// Транзитивное объединение
trel trel::operator+(trel t2)
{
int i, j, k, s;
trel temp;
for (i = 0; i < n; i++)
for (j = 0;j < n; j++)
temp.p[i * n + j] = p[i * n + j] + t2.p[i * n + j];
for (s = 0; s < n; s++)
{
for (k = 0; k < n; k++) temp.c[k] = 0;
//c[s] = 1; // если надо сделать рефлексивным
temp.rec(s);
for (k = 0; k < n; k++) temp.p[s * n + k] = temp.c[k];
}
return temp;
}
// Пересечение
trel trel::operator&(trel t2)
{
int i, j;
trel temp;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
temp.p[i * n + j] = p[i * n + j] & t2.p[i * n + j];
return temp;
}
// Вывод отношения на экран
void trel::show()
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
cout << p[j + i * n];
cout << ‘n';
}
}
int trel::n = 5;
void main()
{
pair pp[]={{1,2},{2,3},{1,4},{4,5}};
pair pq[]={{3,4},{1,3}};
trel t(sizeof(pp)/sizeof(pp[0]),pp);
trel tt(sizeof(pq)/sizeof(pq[0]),pq);
clrscr ();
cout << "Первое отношение:n";
t.show();
cout << "Второе отношение:n";
tt.show();
cout << "Объединение отношений:n";
(t + tt).show();
cout << "Пересечение отношений:n";
(t & tt).show();
getch();
}
Результат работы тестирующей программы
Первое отношение:
01111
00100
00000
00001
00000
Второе отношение:
00110
00000
00010
00000
00000
Объединение отношений:
01111
00111
00011
00001
00000
Пересечение отношений:
00110
00000
00000
00000
00000