*решения произвольных задач на графах, требующих соответствующего порядка обхода ("в глубину") графа; раскрашивая пройденные вершины и/или дуги можно управлять порядком и способами обхода (например, однократное или многократное использование дуг и вершин)
*построения множества истоков и стоков (как истоков на транспонированном графе)
*построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК
Пример задачи на поиск в глубину.
Грядки
Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:
из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.
Входные данные
В первой строке входного файла INPUT.TXT находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. (1 <= N, M <= 200)
Выходные данные
В выходной файл OUTPUT.TXT выведите количество грядок на садовом участке.
Примеры
INPUT.TXT
5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#.
OUTPUT.TXT
3
Основной код
var g:array [1..200,1..200] of char; k,i,j,n,m:integer;
procedure dfs(x,y:longint);
begin
g[x,y]:='o';
if (y<m )and(g[x,y+1]='#') then dfs(x,y+1);
if (y>1 )and(g[x,y-1]='#') then dfs(x,y-1);
if (x<n )and(g[x+1,y]='#') then dfs(x+1,y);
if (x>1 )and(g[x-1,y]='#') then dfs(x-1,y);
end;
begin
readln(n,m);
k:=0;
for i:=1 to n do begin
for j:=1 to m do
read(g[i,j]);
readln;
end;
for i:=1 to n do
for j:=1 to m do begin
if (g[i,j]='#')
then begin
k:=k+1;
dfs(i,j);
end;
end;
writeln(k);
end.