Yolların yeniləməsi (Həll təhlili)

Qeyri-istiqamətli qrafı nəzərdən keçirək və orada əlaqəli komponentləri seçək. Əgər əlaqəli komponent ağacdırsa (yəni dövrə yoxdur), onda kənarları istiqamətləndirmək həmişə mümkündür ki, yalnız bir zirvə çıxan kənarları olmayan qalsın. Bu, o deməkdir ki, əlaqəli ağac komponentində islahatdan sonra mümkün olan minimum təcrid olunmuş şəhər sayı $1$-ə bərabərdir (sıfır mümkün deyil). Məsələn, ağacın kökünü təcrid olunmuş şəhər etmək olar.

Əgər əlaqəli komponentdə dövrə varsa, onda kənarları həmişə elə istiqamətləndirmək mümkündür ki, hər zirvədə ən azı bir çıxan kənar olsun.

Məsələnin cavabı dövrəsiz olan əlaqə komponentlərinin sayıdır.

Nümunə

Birinci nümunəni nəzərdən keçirək. Solda ilkin qraf, sağda isə islahatdan sonra qraf göstərilmişdir. Zirvə $1$ çıxan kənarları olmayan bir zirvədir.

İkinci nümunəni nəzərdən keçirək. Solda ilkin qraf, sağda isə islahatdan sonra qraf göstərilmişdir. Hər zirvədə bir çıxan kənar yerləşdirilmişdir.

Alqoritmin reallaşdırılması

Qrafın strukturunu saxlamaq üçün qonşuluq siyahısı $g$ və artıq ziyarət olunmuş zirvələri qeyd etmək üçün $used$ massivini elan edək.

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

dfs funksiyası $v$ zirvəsindən başlayaraq dərinliyinə axtarış yerinə yetirir. Zirvə $v$-nin əcdadı zirvə $p$-dir.

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

Əgər cari əlaqəli komponentdə dövrə aşkar edilirsə, flag = 0 olaraq təyin olunur.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$m$ kənarını oxuyuruq. Qrafı qururuq.

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

Kəsintisiz qrafda dərinliyinə axtarışı yerinə yetiririk. $res$ dəyişəndə dövrəsiz olan əlaqə komponentlərinin sayı saxlanılır.

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

Hər komponenti emal etməzdən əvvəl flag = 1 olaraq təyin edirik. Əgər gəziş zamanı dövrə aşkar olunarsa, onda dfs çağırışı tamamlandıqdan sonra $flag$ dəyəri $0$ olur.

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

Cavabı çıxardırıq.

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