|
N – количество дуг в орграфе X.
Связанное представление данных: одномерный массив Spisok указателей на структуру index, представляющую собой элемент списка и содержащий поле: целочисленное index (содержит номер вершины, в которую входит дуга) и Next - указатель на структуру Spisok, указывающее на следующий элемент списка
Spisok[ _ ]
NEXT
index
next
index
next
Index
Next
Spisok[ 1 ]
To
…
To
NULL
…
To
…
To
NULL
Spisok[ N ]
To
…
To
NULL
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
При использовании материалов активная ссылка на источник обязательна.