Алгоритм поиска сильно связанных компонент включает нижеследующие процедуры:
strong_components(graph *g)
strong_components(graph *g)
{
int d; /* Счетчик */
for (i=1; i<=(g->nvertices); i++) {
low[i] = i;
scc[i] = -1;
}
components_found = 0;
init_stack(&active);
initialize_search(&g);
for (i=1; i<=(g->nvertices); i++)
if (discovered[i] == FALSE) {
dfs(g,i);
}
}
int low[MAXV+1]; /* Самая старшая вершина наверняка находится в
компоненте вершины v */
int scc[MAXV+1]; /* Номер сильной компоненты для каждой вершины */
process_edge(int х, int у)
{
int class; /* Класс ребра */
class = edge_classification(x,у);
if (class == BACK) {
if (entry_time[y] < entry_time[ low[x] ] )
low[x] = y;
}
if (class == CROSS) {
if (scc[у] = -1) /* Компонента еще не присвоена */
if (entry__time[y] < entry_time[ low[x] ] )
low[x] = у;
}
}
process_vertex_early(int v)
{
push(&active,v);
}
process_vertex_late (int v)
{
if (low[v] == v) { /* Ребро (parent[v],v) отрезает сильно связную компоненту */
pop_component(v);
}
if (entry_time[low[v]] < entry_time[low[parent[v]]])
low [parent [v] ] = low[v];
}
pop_component (int v)
{
int t; /* Заполнитель вершины */
components_found = components_found + 1;
scc[v] = components_found;
while ((t = pop(&active)) != v) {
scc[t] = components_found;
}
}
Если будет нужно напечатать вершины всех компонент, то в какую из процедур нужно вставить операторы печати?