Yanğın Təhlükəsizliyi#1937

Yanğın Təhlükəsizliyi (Həll təhlili)

Verilən məsələdə bütün digər nöqtələrdən keçən qrafın minimum ədədini tapmaq tələb olunur. Bunun üçün qrafın kondensasiyasını gözdən keçirək. Güclü rabitə komponentlərindən heç bir sərhədin çıxmadığına diqqət yetirirəm.

Əgər bu komponentdə yanğın söndürmə stansiyası qurulmazsa, başqa komponentdən gələn yanğın maşını yanğını söndürə bilər, lakin yolu sonunda geriyə qayıda bilməz. Beləliklə, heç bir çıxışı olmayan güclü rabitə komponentində ən azı bir yanğın stansiyası qurmaq lazımdır.

Əlavə stansiya qurmağa ehtiyac yoxdur, çünki qrafın hər hansı bir nöqtəsindən sərhəd olmayan komponentlərdən birinə yol var.

Misal

Girişdəki qraf üç güclü rabitə komponentdən ibarətdir. Ümumi bir nöqtədən ( $4$ və $5$ ) ibarət komponentlərdən heç bir sərhəd çıxılmır. Beləliklə, yanğın söndürmə stansiyalarını yalnız bu komponentlərdə qurmaq kifayətdir.

Alqoritmin tətbiqi

Girişdəki qrafın bitişiklik siyahısında $g$ saxlanılır. Əks qraf (bütün sərhədlərin istiqaməti dəyişdirilən qraf) bitişiklik siyahısında $g r$ saxlanılır.

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

dfs1 funksiyası giriş qrafında dərinli axtarışı həyata keçirir. $t o p$ massivində qrafın dərinli axtarışı sonunda işlənmiş nöqtələrin sırasını saxlayırıq.

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

C++

dfs2 funksiyası əks qrafda dərinli axtarışı həyata keçirir. dfs2 təkrar çağırışın nəticəsində ziyarət edilmiş bütün nöqtələr bir güclü rabitə komponentinə aiddir. Bütün bu nöqtələr $c$ rəngində rənglənir. Bir güclü rabitə komponentinə aid olan nöqtələr eyni rəngə malikdir.

Hər rəng üçün $c$ massivində uyğun komponentin təmsilçisi də saxlanılır —— bu rəngdə rənglənmiş hər hansı nöqtə nömrəsi.

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

Proqramın əsas hissəsi. Giriş məlumatını oxuyuruq. Əks 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ş qrafında dərinli axtarışı başlayırıq. Nöqtələrin işlənmə sırasını $t o p$ massivində saxlayırıq.

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

Əks qrafda dərinli axtarışı başlayın. Əks grafın nöqtələri $t o p$ massivində verilmiş sırada işlənir, bu müddətdə işlənmənin sonundan başlayıb sağdan sola —— massivdən sonuna qədər həyata keçirilir. Maksimallyar işlənmək üçün $t o p$ massivini öncə döndəririk.

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

Bir güclü rabitə komponentinə aid olan nöqtələr eyni rəngə malikdir. Cari rəng $c$ dəyişkənində saxlanılır.

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

$c$ dəyişkəni güclü rabitə komponentlərinin sayını saxlayır.

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

Qrafın bütün sərhədlərini (i, to) sıralayırıq və i və to nöqtələrinin müxtəlif güclü rabitə komponentlərinə aid olub-olmadığını yoxlayırıq. Bu nöqtələrin rəngləri ilə müəyyən edilir. Əgər nöqtələr müxtəlif komponentlərdədirlərsə, $co l or [i]$ color[i] rəngi olan komponentdə yanğın stansiyasını qurmağa ehtiyac yoxdur, buna görə $u se d [co l or [i]] = 0$ used[color[i]] = 0 müəyyən edilir.

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

Yanğın stansiyası qurulması lazım olan komponentlərin sayını $c$ hesablayırıq.

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

Minimum lazımi yanğın stansiyalarının sayını çıxara bilirik.

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

Heç bir sərhəd çıxmayan komponentdə, hər rəng $i$ üçün həmin komponentin təmsilçisini çıxarın (repr[i] qiyməti). Bu ev nömrələridir ki, bunların yanında yanğın stansiyaları qurulmalıdır.

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