Оновлення доріг (Розбір)

Розгляньмо неорієнтований граф та виділимо в ньому компоненти зв'язності. Якщо компонента зв'язності являє собою дерево (тобто не містить циклів), ребра в ній завжди можна орієнтувати так, щоб рівно одна вершина залишилася без вихідних ребер. Це означає, що в компоненті-дереві мінімальна можлива кількість відокремлених міст після реформи дорівнює $1$ (нульова кількість недосяжна). Наприклад, відокремленим містом можна зробити корінь дерева.

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

Відповіддю на задачу буде кількість компонент зв'язності, що не містять циклів.

Приклад

Розгляньмо перший приклад. Ліворуч показано початковий граф, а праворуч — граф після реформи. Вершина $1$ не має вихідних ребер.

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

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

Оголосимо список суміжності $g$ для зберігання структури графа, а також масив $used$ для позначки вже відвіданих вершин.

vector<vector<int> > g;
vector<int> used;

Функція dfs виконує пошук в глибину, починаючи з вершини $v$. Предком вершини $v$ є вершина $p$.

void dfs(int v, int p = -1)
{
  used[v] = 1;
  for (int to : g[v])
  {
    if (to == p) continue;

Якщо в поточній компоненті зв'язності виявляється цикл, встановлюємо flag = 0.

    if (used[to] == 1) flag = 0;
    else dfs(to, v);
  }
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d", &n, &m);
g.resize(n + 1);
used.resize(n + 1);

Читаємо $m$ ребер. Будуємо граф.

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

Виконуємо пошук в глибину на незв'язаному графі. У змінній $res$ зберігається кількість компонент зв'язності, в яких немає циклів.

res = 0;
for (i = 1; i <= n; i++)
{
  if (used[i] == 0)
  {

Перед обробкою кожної компоненти встановлюємо flag = 1. Якщо в процесі обходу буде виявлено цикл, то після завершення виклику dfs значення $flag$ стане рівним $0$.

    flag = 1;
    dfs(i);
    res += flag;
  }
}

Виводимо відповідь.

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