VPF::[Pascal] Теория графов - Форум программистов

Dyatlows

Дата 18.9.2007, 22:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 18.9.2007

Репутация: нет
Всего: нет

Вот! пропустил почти всю тему по теории графов. на паскале...зачот не ставят только из за одной задачки....умы данного форума пожалуйста помогите мне! умоляю....по подсказкам учителки нужное ее решать обходом или в ширину или в глубину...не помню точно. решить надо срочно, очень...буквально к послезавтра край.вот текст самой задачи:
Для каждой вершины графа найти кол-во вершин в ее транзитивном замыкании(транзитивное замыкание-компонента связанности, содержащая заданную вершину).
Помогите умоляю...если нужно задать еще какиенить вопросы...то вот аська и мыло....icq:319737511 мыло:[email protected]

2p0i

Дата 19.9.2007, 21:25 (ссылка)

(голосов:1)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 14.9.2007

Репутация: нет
Всего: 1

Код


const
  maxn = 100;
var
  n, i, j, k: integer;
  inp: text;
  a: array[1..maxn, 1..maxn] of boolean;
  was: array[1..maxn] of boolean;
  comp: array[1..maxn] of integer;
  cnt: array[1..maxn] of integer;

procedure dfs(u: integer);
var
  v: integer;
begin
  was[u] := true;
  comp[u] := k;
  cnt[k] := cnt[k] + 1;
  for v := 1 to n do
    if not was[v] and a[u, v] then
      dfs(v);
end;

begin
  assign(inp, 'graph.txt');
  reset(inp);
  read(inp, n);
  for i := 1 to n do
    for j := 1 to n do
      a[i, j] := false;
  while not seekeof(inp) do begin
    read(inp, i, j);
    a[i, j] := true;
    a[j, i] := true;
  end;
  close(inp);

  for i := 1 to n do
    was[i] := false;
  k := 0;
  for i := 1 to n do
    if not was[i] then begin
      k := k + 1;
      cnt[k] := 0;
      dfs(i);
    end;

  for i := 1 to n do
    writeln(i, '-', cnt[comp[i]]);
end.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »