2009. - 109 с ..
Додаток
Лістинг програми
# include N;// Кількість вершин у графі
# define MAX_NODES 100// Максимальна кількість вершин
# define MAX_EDGES 10// Максимальна кількість ребер, що виходять з однієї вершіниedges [MAX_NODES] [MAX_EDGES];// Граф, в якому шукаємо сильно зв'язкові компоненти
int edges_c [MAX_NODES]; edgesT [MAX_NODES] [MAX_EDGES];// транспонировании графedgesT_c [MAX_NODES];
int state [MAX_NODES];// Використовується в пошуку для того щоб відзначати відвідані вершіниf [MAX_NODES], last_f = 0;// Список попередньої розстановки вершінc = 1;// Номер компоненти (збільшуємо його , коли знаходимо нову)
void dfs (int node) {[node] = 1;
for (int i = 0; i
} dfsT (int node) {[node] = 1;
for (int i = 0; i
dfsT (edgesT [node] [i]);// заходячи в кожну ("% d% d n", node, c);
} scc () {//Strongly Connected Components - функція виділення сильно зв'язкових компонент графаi; (i = 0; i
dfs (i);// Попередня розстановка вершин.
for (i = 0; i = 0; last_f -)// 2-ий пошук в глибину ( state [f [last_f]] == 0) {//...
dfsT (f [last_f]);// Остаточне виділення сильно зв'язкових компонент + +;// збільшуємо номер наступної компоненти
}
} main () {i; ("% d", & N); (i = 0; i
edges [i] [j] = to;// Побудова вихідного графа [to] [edgesT_c [to] + +] = i;// Побудова транспоновану графа
}
} ();// Знайти і вивести сильно зв'язкові компоненти0;
}
Топологічна сортування
# include
# include
# include
# define M 15
# define N 1000
# define NE 100
# define P 10007
