Qrafın kondensasiyası#1947

Qrafın kondensasiyası (Həll təhlili)

Qrafın güclü əlaqəli komponentlərini tapırıq. Hər bir güclü əlaqəli komponentin bütün təpələrini unikal bir rəngə boyayırıq. Qoy $co l or [i]$ color[i] — $i$ -ci təpənin rəngi olsun. İstifadə olunan rənglərin sayı güclü əlaqəli komponentlərin sayına bərabərdir.

Əsas qrafın bütün kənarlarını yoxlayırıq. Əgər kənar fərqli rənglərə malik təpələri birləşdirirsə, o, qrafın kondensasiyasındakı kənara uyğun gəlir. Hər bir $(a, b)$ kənarı üçün, əgər $co l or [a] \neq = co l or [b]$ color[a] \ne color[b], onda $s$ çoxluğuna $(co l or [a], co l or [b])$ (color[a], color[b]) cütlüyünü əlavə edirik. Çoxluqdan istifadə edildiyi üçün, çoxlu cütlər nəzərə alınmayacaq.

Çoxluq $s$ -dakı elementlərin sayı qrafın kondensasiyasındakı kənarların sayına bərabərdir.

Misal

Misalda verilən qraf bu cür görünüşə malikdir:

Qrafın kondensasiyası üç təpə və iki kənardan ibarətdir.

Alqoritmin reallaşdırılması

Giriş qrafını $g$ qonşuluq siyahısında saxlayırıq. Tərs qrafı (bütün kənarların istiqamətləri təkrarlanmış qraf) $g r$ qonşuluq siyahısında saxlayırıq. Kondensasiya olunmuş qrafın kənarlarını cütlük $s$ çoxluğunda saxlayacağıq.

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

dfs1 funksiyası daxil olan qrafda dərinlik üzrə axtarış həyata keçirir. Dərinlik üzrə axtarış alqoritminin qurtarmaq ardıcıllığında işlədilən təpələri $t o p$ massivində qeyd edirik.

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

C++

dfs2 funksiyası tərs qrafda dərinlik üzrə axtarıldığını həyata keçirir. dfs2 funksiyasının rekursiv çağırışı zamanı ziyarət edilən bütün təpələr bir güclü əlaqəli komponentə aiddir. Bütün bu təpələri rəng $с$ ilə boyayırıq.

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

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq. Tərs qraf qururuq.

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++

Giriş qrafda dərinlik üzrə axtarışa başlayırıq. Təpələrin işlənmə qurtarma ardıcıllığı $t o p$ massivində saxlanılır.

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

Tərs qrafda dərinlik üzrə axtarışa başlayırıq. Tərs qrafın təpələri $t o p$ massivinə əks ardıcıllıqda (son elementdən birinciyə qədər) nəzərə alınır. Əlavə əməliyyatların asanlığı üçün $t o p$ massivini tərsinə çeviririk.

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

Bir güclü əlaqəli komponentə aid olan təpələri eyni rəngə boyayırıq. Cari rəng $с$ dəyişənində saxlanılır.

c = 0;

Daha sonra $t o p$ massivini soldan sağa keçib, hələ boyanmamış hər bir təpədən dərinlik üzrə axtarış dfs2-ni başlatırıq.

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

Dəyişən $c$ güclü əlaqəli komponentlərin sayını saxlayır. Əsas qrafın bütün $(i, t o)$ kənarlarını yoxlayırıq.

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

Təpə $i$ və $t o$ -nun fərqli güclü əlaqəli komponentlərə aid olub-olmadığını yoxlayırıq, yəni onların fərqli rənglərə boyanıb-boyanmadığını yoxlayırıq. Əgər bu belədirsə, onda $(i, t o)$ kənarı qrafın kondensasiyasına aid edilir, buna görə də $s$ çoxluğuna $(co l or [i], co l or [t o])$ (color[i], color[to]) cütlüyünü əlavə edirik. Çoxluqdan istifadə edildiyi üçün, çoxlu cütlər nəzərə alınmayacaq.

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

Qrafın kondensasiyasındakı kənarların sayını çap edirik.

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