3. Поиск в глубину

Разбор задачи 1269. Саванна

Тема: поиск в глубину

Для работы потребуются следующие переменные:

var n, { количество животных }
  d,   { максимальное расстояние между животными одного стада }
  k,   { количество стад }
  i:longint;

  x,y:array[1..1000] of longint; { координаты животных }

  f:array[1..1000] of boolean; { флажки - животное отнесено к какому-то стаду }

Эти переменные инициализируются следующим образом:

read(n,d);
for i:=1 to n do
  begin
    read(x[i],y[i]);
    f[i]:=false;
  end;
k:=0;

Для отнесения животного к какому-то стаду используем рекурсивную подпрограмму:

procedure dfs(i:integer);
var j:integer;
begin
  if f[i] then exit; { уже классифицировали - выходим }
  f[i]:=true; { отмечаем флажком }
  for j:=1 to n do 
    { для всех животных на расстоянии не более D }
    if sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(d) then
      dfs(j); { делаем те же действия }
end;

Теперь для всех непомеченных животных вызываем эту подпрограмму и увеличиваем счетчик стад `k`:

for i:=1 to n do
  if not f[i] then
    begin
      inc(k);
      dfs(i);
    end;

После завершения цикла выводим значение `k`.