Invertire il grafo (Editoriale)

Costruiamo un grafo 0 - 1, assegnando agli archi esistenti il peso $0$, e ai loro archi inversi il peso $1$. Successivamente eseguiamo una ricerca in ampiezza. La lunghezza del cammino più breve dal vertice $1$ al vertice $n$ sarà uguale al numero minimo di archi che devono essere invertiti.

Esempio

Il grafo riportato nell'esempio si presenta come segue:

Implementazione dell'algoritmo

Dichiariamo una costante infinito.

#define INF 0x3F3F3F3F

Dichiariamo l'array delle distanze minime $dist$ e la lista di adiacenza del grafo $g$. Per ogni arco, insieme al vertice adiacente, memorizziamo il peso dell'arco ($0$ o $1$).

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

La funzione bfs implementa la ricerca in ampiezza a partire dal vertice $start$.

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;

A seconda del peso dell'arco $w$, aggiungiamo il vertice $to$ alla fine o all'inizio della coda.

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

Parte principale del programma. Leggiamo i dati in ingresso.

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

All'arco orientato a → b assegniamo il peso $0$, all'arco inverso assegniamo il peso $1$.

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

Eseguiamo la ricerca in ampiezza a partire dal vertice $1$.

bfs(1);

Stampiamo la risposta — la distanza minima fino al vertice $n$.

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