Компоненты сильной связности
Санек 20 ноя 2012
Компонентой сильной связности (strongly connected component) называется такое максимальное подмножество вершин графа, что если мы возьмем любое две вершины, то есть путь как из одной в другую, так и обратно.
Задача
Дан граф (n вершин и m ребер). Далее идут описания ребер, т.е. две вершины, из которой в какую есть путь (ребро). Найти все компоненты сильной связности (их количество).
Словесный алгоритм
Топологическая сортировка
Меняем направление ребер
Ищем кол-во к.с.с
Сам dfs2
Не забудьте обнулить массив меток used перед поиском к.с.с.
Сообщение отредактировал Санек: 20 ноября 2012 - 17:50
Задача
Дан граф (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