Qrafiki genişləndirin (Həll təhlili)

0-1 qrafı quraq: mövcud tillərə $0$ çəkisini, onların əks tillərinə isə $1$ çəkisini verək. Sonra enliliyinə axtarış (BFS) işə salaq. $1$ təpəsindən $n$ təpəsinə ən qısa yolun uzunluğu tərs çevrilməli olan tillərin minimal sayına bərabər olacaqdır.

Nümunə

Nümunədə verilmiş qraf aşağıdakı kimidir:

Alqoritmin realizasiyası

Sonsuzluq sabitini elan edək.

#define INF 0x3F3F3F3F

Ən qısa məsafələr massivi $dist$-i və qrafın qonşuluq siyahısı $g$-ni elan edək. Hər til üçün qonşu təpə ilə birlikdə tilin çəkisini ($0$ və ya $1$) saxlayırıq.

vector\<int\> dist;
vector\<vector\<pair\<int, int\> \> \> g;

bfs funksiyası $start$ təpəsindən enliliyinə axtarışı realizasiya edir.

void bfs(int start)
{
  dist = vector\<int\>(n + 1, INF);
  dist[start] = 0;

  deque\<int\> q;
  q.push_back(start);

  while (!q.empty())
  {
    int v = q.front(); q.pop_front();
    for (auto edge : g[v])
    {
      int to = edge.first;
      int w = edge.second;
      if (dist[to] \> dist[v] + w)
      {
        dist[to] = dist[v] + w;

Tilin $w$ çəkisindən asılı olaraq $to$ təpəsini növbənin sonuna və ya əvvəlinə əlavə edirik.

        if (w == 1)
          q.push_back(to);
        else
          q.push_front(to);
      }
    }
  }
}

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

scanf("%d %d", \&n, \&m);
g.resize(n + 1);
for (i = 0; i \< m; i++)
{
  scanf("%d %d", \&a, \&b);

Yönəldilmiş a → b tilinə $0$ çəkisini, əks tilə isə $1$ çəkisini veririk.

  g[a].push_back({ b, 0 });
  g[b].push_back({ a, 1 });
}

$1$ təpəsindən enliliyinə axtarışı işə salırıq.

bfs(1);

Cavabı — $n$ təpəsinə qədər olan ən qısa məsafəni çap edirik.

if (dist[n] == INF)
  printf("-1\n");
else
  printf("%d\n", dist[n]);