Головна

Пошук точок зчленування

  1. Акустичний метод пошуку кабелю в разі іскрового розряду в місці пошкодження кабелю
  2. Алгоритм пошуку компонент зв'язності в графі
  3. БАЗИ ДАНИХ, ІНФОРМАЦІЙНО-ДОВІДКОВІ І ПОШУКОВІ СИСТЕМИ
  4. Квиток 16. Поняття істини. Проблема критеріїв істини. Діагностичний процес як пошук істини.
  5. У чому полягають пошуки об'єктивного критерію періодизації розвитку суспільства?
  6. в) бази даних, інформаційно-довідкові та пошукові системи
  7. Замість точок вставте одне з займенників little, a little, few, a few.

Нехай дано зв'язний неорієнтований граф. Точкою зчленування (або точкою артикуляції, англ. "Cut vertex" або "articulation point") називається така вершина, видалення якої робить граф незв'язним.

vector g [MAXN];

bool used [MAXN];

int timer, tin [MAXN], fup [MAXN];

void dfs (int v, int p = -1) {

used [v] = true;

tin [v] = fup [v] = timer ++;

int children = 0;

for (size_t i = 0; i

int to = g [v] [i];

if (to == p) continue;

if (used [to])

fup [v] = min (fup [v], tin [to]);

else {

dfs (to, v);

fup [v] = min (fup [v], fup [to]);

if (fup [to]> = tin [v] && p! = -1)

IS_CUTPOINT (v);

++ Children;

}

}

if (p == -1 && children> 1)

IS_CUTPOINT (v);

}

int main () {

int n;

... Читання n і g ...

timer = 0;

for (int i = 0; i

used [i] = false;

dfs (0);

}

тут константі  має бути встановлено значення, рівне максимально можливого числа вершин у вхідному графі.

функція  в коді - це якась функція, яка буде реагувати на те, що вершина  є точкою зчленування, наприклад, виводити цю вершини на екран (треба враховувати, що для однієї і тієї ж вершини ця функція може бути викликана кілька разів).

8) Дейкстра

const int INF = 1000000000;

int main () {

int n;

... Читання n ...

vector >> g (n);

... Читання графа ...

int s = ...; // Стартова вершина

vector d (n, INF), p (n);

d [s] = 0;

vector u (n);

for (int i = 0; i

int v = -1;

for (int j = 0; j

if (! u [j] && (v == -1 || d [j]

v = j;

if (d [v] == INF)

break;

u [v] = true;

for (size_t j = 0; j

int to = g [v] [j] .first,

len = g [v] [j] .second;

if (d [v] + len

d [to] = d [v] + len;

p [to] = v;

}

}

}

}

9) Ератосфен

int n;

vector prime (n + 1, true);

prime [0] = prime [1] = false;

for (int i = 2; i <= n; ++ i)

if (prime [i])

if (i * 1ll * i <= n)

for (int j = i * i; j <= n; j + = i)

prime [j] = false;

Задача про призначення

Завдання має дві еквівалентні постановки:

Дана квадратна матриця A [1..N, 1..N]. Потрібно вибрати в ній N елементів так, щоб в кожному рядку і стовпці був обраний рівно один елемент, а сума значень цих елементів була найменшою.

Є N замовлень і N верстатів. Про кожне замовлення відома вартість його виготовлення на кожному верстаті. На кожному верстаті можна виконувати тільки одне замовлення. Потрібно розподілити всі замовлення по верстатах так, щоб мінімізувати сумарну вартість.

vector u (n + 1), v (m + 1), p (m + 1), way (m + 1);

for (int i = 1; i <= n; ++ i) {

p [0] = i;

int j0 = 0;

vector minv (m + 1, INF);

vector used (m + 1, false);

do {

used [j0] = true;

int i0 = p [j0], delta = INF, j1;

for (int j = 1; j <= m; ++ j)

if (! used [j]) {

int cur = a [i0] [j] -u [i0] -v [j];

if (cur

minv [j] = cur, way [j] = j0;

if (minv [j]

delta = minv [j], j1 = j;

}

for (int j = 0; j <= m; ++ j)

if (used [j])

u [p [j]] + = delta, v [j] - = delta;

else

minv [j] - = delta;

j0 = j1;

} While (p [j0]! = 0);

do {

int j1 = way [j0];

p [j0] = p [j1];

j0 = j1;

} While (j0);

}

 



Алгоритм пошуку компонент зв'язності в графі | Алгоритм Куна знаходження найбільшого паросполучення в дводольному графі

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

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