Usmeravanje puteva - Rešenje

Postavka

Problem se sasvim direktno modeluje neusmerenim grafom u kom su čvorovi tačke u gradu, a grane dvosmerni putevi između njih. Po pretpostavkama zadatka polazni graf je povezan.

Ključni uvid za rešenje zadatka je da je usmeravanje puteva moguće ako i samo ako u grafu ne postoji most. Naime, ako u grafu postoji most, kako god da ga usmerimo, neće postojati drugi put između dela drveta iznad i ispod tog mosta. Ako u grafu ne postoji most, tada je moguće usmeriti sve grane drveta naniže, a sve povratne grane naviše, čime bi se dobila veza između svih čvorova grafa. Naime, pošto je polazni graf povezan, od korena je moguće kroz drvo stići do bilo kog čvora drveta (tj. grafa). Od svakog čvora je moguće povratnom granom vratiti se u neki deo drveta “ispod” tog čvora, pa se krećući se na taj način može stići i do korena. Dakle, bilo koji čvor i koren su obostrano dostižni, pa su i svi čvorovi međusobno obostrano dostižni.

Pošto se tokom određivanja mostova pamte roditelji svih čvorova, grane drveta možemo, na primer, prepoznati korišćenjem niza roditelja.

// određujemo sve mostove grafa
dfs_mostovi(0);

if (mostovi.size() > 0)
  // ako u grafu ima mostova, ulice se ne mogu usmeriti
  cout << 0 << endl;
else {
  // u grafu nema mostova, pa usmeravamo grane drveta "naviše", a
  // povratne grane "naniže"
  for (int cvor = 0; cvor < n; cvor++)
    for (int sused : listaSuseda[cvor]) {
      // u neusmerenom grafu je svaka grana predstavljena dva puta
      // ovim se obezbeđuje da će se svaka grana razmatrati samo jednom
      if (cvor > sused) continue;
      // (u, v) je ta grana usmerena od pretka ka potomku
      int u = cvor, v = sused;
      if (dolazna[u] > dolazna[v])
        swap(u, v);

      // usmeravamo granu na pravi način
      if (roditelj[v] == u)
        // grana drveta
        cout << u+1 << " " << v+1 << endl;
      else
        // povratna grana
        cout << v+1 << " " << u+1 << endl;
    }
}
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> listaSuseda;
int vreme_dolazna = 0;
vector<int> dolazna;
vector<int> lowlink;
vector<int> roditelj;
vector<pair<int, int>> mostovi;


void dfs_mostovi_rek(int cvor) {
  // dodeljujemo redni broj cvoru 'cvor'
  dolazna[cvor] = vreme_dolazna++;
  // inicijalizujemo vrednost funkcije L cvora 'cvor' na njegov redni broj
  lowlink[cvor] = dolazna[cvor];
  
  // rekurzivno prolazimo kroz sve susede koje nismo obisli
  for (auto sused : listaSuseda[cvor]) {
    // ukoliko je sused vec posecen 
    if (dolazna[sused] != -1) {
      // ako grana ne vodi ka roditelju datog cvora
      if (sused != roditelj[cvor])
         // po potrebi azuriramo vrednost L cvora na redni broj suseda
         if (dolazna[sused] < lowlink[cvor])
             lowlink[cvor] = dolazna[sused];
    } else {
    // ukoliko sused nije posecen

      // pamtimo granu DFS drveta
      roditelj[sused] = cvor;
      // pokrecemo pretragu iz cvora 'sused'
      dfs_mostovi_rek(sused);

      // nakon obrade poddrveta čiji je koren cvor 'sused' vrednost L cvora 'sused' je odredjena
      // po potrebi azuriramo vrednost L za cvor 'cvor'
      if (lowlink[sused] < lowlink[cvor])
               lowlink[cvor] = lowlink[sused];

      // proveravamo da li je grana (cvor, sused) most
      // u ovom trenutku su vrednosti L cvora 'sused' i rednog broja cvora 'cvor` odredjene
      if (lowlink[sused] > dolazna[cvor])
        mostovi.emplace_back(cvor, sused);
    }
  }
}

void dfs_mostovi(int cvor) {
  int n = listaSuseda.size();
  dolazna.resize(n, -1);
  roditelj.resize(n, -1);
  lowlink.resize(n);
  dfs_mostovi_rek(0);
}


int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  listaSuseda.resize(n);
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    listaSuseda[a-1].push_back(b-1);
    listaSuseda[b-1].push_back(a-1);
  }
  // određujemo sve mostove grafa
  dfs_mostovi(0);

  if (mostovi.size() > 0)
    // ako u grafu ima mostova, ulice se ne mogu usmeriti
    cout << 0 << endl;
  else {
    // u grafu nema mostova, pa usmeravamo grane drveta "naviše", a
    // povratne grane "naniže"
    for (int cvor = 0; cvor < n; cvor++)
      for (int sused : listaSuseda[cvor]) {
        // u neusmerenom grafu je svaka grana predstavljena dva puta
        // ovim se obezbeđuje da će se svaka grana razmatrati samo jednom
        if (cvor > sused) continue;
        // (u, v) je ta grana usmerena od pretka ka potomku
        int u = cvor, v = sused;
        if (dolazna[u] > dolazna[v])
          swap(u, v);

        // usmeravamo granu na pravi način
        if (roditelj[v] == u)
          // grana drveta
          cout << u+1 << " " << v+1 << endl;
        else
          // povratna grana
          cout << v+1 << " " << u+1 << endl;
      }
  }
  return 0;
}