Протипожежна безпека#1937

Протипожежна безпека (Розбір)

У задачі потрібне знайти мінімальну множину вершин графа, досяжну з усіх інших вершин. Для цього розглянемо конденсацію графа. Звернемо увагу на компоненти сильної зв'язності, з яких не виходить жодного ребра.

Якщо в такій компоненті не збудувати пожежну станцію, то пожежна машина, що приїхала з іншої компоненти, зможе загасити пожежу, однак повернутися назад, слідуючи напрямкам доріг, вже не зможе. Згідно з цим, у кожній компоненті сильної зв'язності без вихідних ребер необхідно побудувати хоча б одну пожежну станцію.

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

Приклад

Вхідний граф містить три компоненти сильної зв'язності. З компонент, що складаються з однієї вершини ( $4$ і $5$ ), не виходить жодного ребра. Згідно, достатньо побудувати пожежні станції саме в цих компонентах.

Реалізація алгоритму

Вхідний граф зберігаємо у списку суміжності $g$ . Оборотний граф (граф, в якому напрямки всіх ребер інвертовані) зберігаємо у списку суміжності $g r$ .

vector<vector<int> > g, gr;
vector<int> used, top, color, repr;

Функція dfs1 реалізує пошук у глибину на вхідному графі. У масиві $t o p$ зберігаємо порядок вершин, що відповідає моменту завершення їх обробки при обході в глибину.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

C++

Функція dfs2 реалізує пошук у глибину на оборотному графі. Всі вершини, відвідані в результаті рекурсивних викликів dfs2, належать одній компоненті сильної зв'язності. Всі такі вершини фарбуються кольором $c$ . Вершини, що належать одній компоненті сильної зв'язності, мають однаковий колір.

Для кожного кольору $c$ в масиві $r e p r$ зберігається представник відповідної компоненти — будь-який номер вершини, пофарбованої цим кольором.

void dfs2(int v, int c)
{
  color[v] = c;
  repr[c] = v;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, c);
}

C++

Основна частина програми. Читаємо вхідні дані. Будуємо оборотний граф.

scanf("%d %d", &n, &m);
g.resize(n + 1);
gr.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b); 
  gr[b].push_back(a);
}

C++

Запускаємо пошук у глибину на вихідному графі. Порядок, у якому завершується обробка вершин, зберігаємо у масиві $t o p$ .

used.resize(n+1);
for (i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

Запускаємо пошук у глибину на оборотному графі. Вершини оборотного графа оброблюються у порядку, заданому у масиві $t o p$ , при цьому обход виконується справа наліво — від кінця масиву до початку. Для зручності подальшої обробки масива $t o p$ попередньо розгортаємо.

color.assign(n+1, -1);
repr.assign(n+1, -1);
reverse(top.begin(), top.end());

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

c = 0;
for (int v : top)
  if (color[v] == -1) dfs2(v, c++);

Змінна $c$ містить кількість компонент сильної зв'язності.

used.assign(c, 1);
for (i = 1; i < g.size(); i++)
  for (int to : g[i])

Перебираємо всі ребра графа $(i, t o)$ і перевіряємо, чи належать вершини $i$ та $t o$ різним компонентам сильної зв'язності. Це визначається за різними кольорами вершин. Якщо вершини знаходяться в різних компонентах, у компоненті з кольором $co l or [i]$ color[i] немає необхідності будувати пожежну станцію, тому встановлюємо $u se d [co l or [i]] = 0$ used[color[i]] = 0.

  if (color[i] != color[to]) used[color[i]] = 0;
}

Підрахуємо кількість компонент $c$ , в яких слід побудувати пожежну станцію.

c = 0;
for (i = 0; i < used.size(); i++)
  if (used[i]) c++;

Виводимо мінімальне необхідне число пожежних станцій.

printf("%d\n",c);

Для кожної компоненти з кольором $i$ , з якої не виходить жодного ребра, виводимо її представника (значення $r e p r [i]$ repr[i]). Саме ці номери будинків вказують, біля яких слід побудувати пожежні станції.

for (i = 0; i < used.size(); i++)
  if (used[i]) printf("%d ",repr[i]);
printf("\n");