Задча на граф Опции

[r-d-v2008]

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

[volvo]

Вообще-то задачу дали тебе, а не мне, правда?

Вот так реализуется алгоритм:

function f(const mx: TIncidence): boolean;
var
  count: integer;
  i, Vx: Vertexes;
  found: boolean;
  p: PList;
begin
  f := false;

  count := 0;
  for i := 1 to LastVertex do
    if mx[i] = nil then
    begin
      Inc(count); Vx := i;
    end;

  if count > 1 then exit { <-- result = false }
  else begin

    for i := 1 to LastVertex do
      if i <> Vx then
      begin
        p := mx[i];
        found := false;
        while (p <> nil) and (not found) do
        begin
          if p^.Vertex = Vx then found := true;
          p := p^.next;
        end;

        if not found then exit; { <-- result = false }
      end;

  end;

  f := true;
end;

Но чтобы проверить его работоспособность, тебе придется самому описать тип TIncidence и все остальные, а также написать основную программу так, чтобы эта программа хотя бы откомпилировалась. Кроме этого, матрицу инцидентности еще придется заполнить, чтобы проверить, правильно ли функция отрабатывает (на нескольких вариантах, разумеется, когда она должна возвращать "истину", и когда - "ложь"). Но все это - уже самостоятельно. Я ни за кого задачи не решаю полностью. Халявы не будет...