Головна

Алгоритм пошуку компонент зв'язності в графі

  1. II. Правила орфографії, пов'язані з фонемно-графемно
  2. Акустичний метод пошуку кабелю в разі іскрового розряду в місці пошкодження кабелю
  3. алгоритм
  4. алгоритм
  5. Алгоритм 4.2. Ліва факторізація граматики
  6. Алгоритм 5.2. Побудова табліці предиктивного АНАЛІЗУ

Дан неорієнтовані граф с  вершинами і  ребрами. Потрібно знайти в ньому всі компоненти зв'язності, тобто розбити вершини графа на кілька груп так, що всередині однієї групи можна дійти від однієї вершини до будь-якої іншої, а між різними групами - шляху не існує.

int n;

vector g [MAXN];

bool used [MAXN];

vector comp;

void dfs (int v)

(...)

void find_comps () {

for (int i = 0; i

used [i] = false;

for (int i = 0; i

if (! used [i]) {

comp.clear ();

dfs (i);

cout << "Component:";

for (size_t j = 0; j

cout << '' << comp [j];

cout << endl;

}

}

 



Флойд-Уоршелл | Пошук точок зчленування

Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі | Розширений Евклід | дискретного логарифмування | Теорема Піка. | Z-функція рядка і її обчислення | Знаходження наідліннейшей зростаючої підпослідовності | Знаходження найбільшою нульовий подматріци | Біноміальні коефіцієнти | числа Каталана | намиста |

© um.co.ua - учбові матеріали та реферати