Конденсація графа#1947

Конденсація графа (Розбір)

Знаходимо компоненти сильної зв'язності графа. Усі вершини кожної компоненти сильної зв'язності фарбуємо в один унікальний колір. Нехай $co l or [i]$ color[i] — колір $i$ -ї вершини. Кількість використаних кольорів дорівнює числу компонент сильної зв'язності.

Перебираємо всі ребра вихідного графа. Якщо ребро з'єднує вершини різних кольорів, то воно відповідає ребру в конденсації графа. Для кожного ребра $(a, b)$ , такого що $co l or [a] \neq = co l or [b]$ color[a] \ne color[b], додамо в множину $s$ пару $(co l or [a], co l or [b])$ (color[a], color[b]). Оскільки використовується множина, а не мультимножина, кратні пари враховуватися не будуть.

Кількість елементів у множині $s$ дорівнює числу ребер в конденсації графа.

Приклад

Граф, наведений у прикладі, має наступний вигляд:

Конденсація графа складається з трьох вершин і двох ребер.

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

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

vector\<vector\<int\> \> g, gr;
vector\<int\> used, top, color;
set\<pair\<int,int\> \> s;

Функція 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, належать одній компоненті сильної зв'язності. Усі такі вершини фарбуємо в колір $с$ .

void dfs2(int v, int c)
{
  color[v] = c;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, 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);
reverse(top.begin(), top.end());

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

c = 0;

Далі проходимо по масиву $t o p$ зліва направо і з кожної ще не забарвленої вершини запускаємо пошук в глибину dfs2.

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

Змінна $c$ містить кількість компонент сильної зв'язності. Перебираємо всі ребра вихідного графа $(i, t o)$ .

for (i = 1; i \< g.size(); i++)
for (int to : g[i])

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

  if (color[i] != color[to])
    s.insert(make_pair(color[i], color[to]));

Виводимо кількість ребер в конденсації графа.

printf("%d\n",s.size());