1. Постановка задачи.

Дано:

Два орграфа X и Y с N вершинами (X в последовательном представлении, Y в связанном представлении) без кратностей. Дуги орграфов образуют неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин, в которые ведут ребра из каждой вершины графа.

Требуется:

Выполнить над ребрами орграфов операцию разности(X/Y). В результате выполнения этой операции новый орграф Zопределяется в связанном представлении, а старый орграф Xисправляется в последовательном представлении.

Особенности представления данных:

Последовательное представление данных: одномерный массив Array, содержащую два целочисленных поля I(содержит номер вершины, из которой исходит дуга) и J (содержит номер вершины, в которую входит дуга).

N – количество дуг в орграфе X.

Связанное представление данных: одномерный массив Spisok указателей на структуру index, представляющую собой элемент списка и содержащий поле: целочисленное index (содержит номер вершины, в которую входит дуга) и Next- указатель на структуру Spisok, указывающее на следующий элемент списка

N - количество вершин в графе Y,Z.

2. Внешнее описание программы.

Ввод информации об неориентированных графах происходит из файла, формат которого должен быть нижеследующим:

N

X11 X12 . X1k1 0

X21 X22 . X2k2 0

.

XN1 XN2 . XNkN 0

Y11 Y12 . Y1k1 0

Y21 Y22 . Y2k2 0

.

YN1 YN2 . YNkN 0

где N - число вершин в графах

Xij - номер очередной вершины смежной i в графе X (i = 1 N, j=1 ki)

Yij - номер очередной вершины смежной i в графе Y(i = 1 N, j=1 ki)

Если из какой-то вершины не выходит ни одного ребра, то для нее в исходных данных задаем только ноль (например ‘0’ - вершина 2 изолирована). Таким образом, для каждого графа должно вводится в общей сложности N нолей.

Формат печати результатовработы программы представлен в следующем формате:

Даны неориентированные графы X и Y без кратностей.

Для каждого графа задаем номера вершины смежности с данной.

Граф X (в ЭВМ в последовательном представлении):

1 : X11 X12 . X1k1

2 : X21 X22 . X2k2

.

N : XN1 XN2 . XNkN

Граф Y (в ЭВМ в связанном представлении):

1 : Y11 Y12 . Y1k1

2 : Y21 Y22 . Y2k2

.

N : YN1 YN2 . YNkN

Над графами выполняется операция разности двумя способами

с получением нового графа Z (в связанном представлении):

1 : Z11 1,Z12 . Z1k1

2 : Z21 Z22 . Z2k2

.

N : ZN1 ZN2 . ZNkN

И исправлением старого графа X (в последовательном представлении):

1 : X11 X12 . X1k1

2 : X21 X22 . X2k2

.

N : XN1 XN2 . XNkN

Кол-во вершин, кол-во дуг графа X, кол-во дуг графа Y

и кол-во времени, затраченного на вычисление разности X и Y:

N MX MY T

где T - кол-во времени, затраченного на вычисление разности X и Y

Zij - номер очередной вершины смежной i в графе Z(i = 1 N, j=1 ki)

MX - кол-во дуг в графе X

MY - кол-во дуг в графе Y

Метод решения:

Принцип решения основан на методе полного перебора, что конечно не лучший вариант, но все-таки лучше, чем ничего.

Аномалии исходных данных и реакция программы на них:

1. нехватка памяти при распределение: вывод сообщения на экран и завершение работы программы;