Задача
Дан граф (n вершин и m ребер). Далее идут описания ребер, т.е. две вершины, из которой в какую есть путь (ребро). Найти все компоненты сильной связности (их количество).
Словесный алгоритм
- Сортируем вершины топологически.
- Инвертируем граф (т.е. меняем направления ребер, например если было ребро из 2 в 3 вершину, то делаем из 3 во 2)
- Пробегаемся по отсортированному массиву и если находим не помеченную вершину, то увеличиваем счетчик кол-во к.с.с. и пускаем dfs2 от этой вершины
Топологическая сортировка
procedure dfs(v:longint); var i:longint; begin used[v]:=true;//помечаем вершину for i:=1 to n do //перебираем все вершины if not(used[i]) and (g[v,i]=1) then dfs(i); //если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины cnt:=cnt+1;//кол-во вершин тоположке dag[cnt]:=v; //кидаем нашу вершину в топологически отсортированный массив end;
Меняем направление ребер
for i:=1 to n do for j:=1 to n do if (g[i,j]=1) then g1[j,i]:=1; //здесь думаю все понятно
Ищем кол-во к.с.с
scc:=0; for i:=cnt downto 1 do if not(used[dag[i]]) //если вершина не помеченна then begin scc:=scc+1; //на 1 увеличиваем кол-во к.с.с. dfs2(dag[i]); //пускаем dfs2 от нашей вершины end; writeln(scc);
Сам dfs2
procedure dfs2(v:longint); var i:longint; begin used[v]:=true; //помечаем вершину for i:=1 to n do//перебираем все вершины if not(used[i]) and (g1[v,i]=1) then dfs2(i);//если вершина не помеченна и есть путь из нашей вершину в нее, то запускаем глубину от этой вершины end;
Не забудьте обнулить массив меток used перед поиском к.с.с.
Сообщение отредактировал Санек: 20 ноября 2012 - 17:50