Usmeravanje puteva

U jednom gradu su ulice uske i stvara se gužva u saobraćaju. Gradske vlasti su odlučile da sve ulice postanu jednosmerne, u nadi da će se time povećati protočnost, međutim, nisu sigurni da li je moguće da usmere puteve tako da se i dalje može stići od bilo koje, do bilo koje druge tačke u gradu.

Opis ulaza

Sa standardnog ulaza se učitava broj tačaka u gradu \(n\) (1 ≤ \(n\) ≤ 105), a zatim broj dvosmernih puteva između njih \(m\) (1 ≤ \(m\) ≤ 105). U narednih \(m\) linija nalaze se po dva različita broja \(a_i\) i \(b_i\) (1 ≤ \(a_i\), \(b_i\) ≤ \(n\), \(a_i\) ≠ \(b_i\)), koji predstavljaju redne brojeve tačaka spojenih ulicom.

Opis izlaza

Na standardni izlaz ispisati 0 ako nije moguće usmeriti ulice ili \(m\) parova tačaka koji predstavljaju usmerene ulice.

Primer 1

Ulaz

3
3
1 2
2 3
1 3

Izlaz

1 2
2 3
3 1

Primer 2

Ulaz

4
4
1 2
2 3
3 1
1 4

Izlaz

0

Rešenje

Opis glavnog rešenja

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, prepo- znati korišćenjem niza roditelja.

#include <iostream>
#include <vector>

using namespace std;

void dfs_mostovi(int cvor, int &vreme_dolazna, vector<bool> &posecen, vector<int> &dolazna, vector<int> &lowlink,
                 vector<int> &roditelj, vector<pair<int, int>> &mostovi, vector<vector<int>> &listaSuseda) {
   // dodeljujemo redni broj cvoru 'cvor'
   posecen[cvor] = true;
   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 (posecen[sused]) {

         // 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(sused, vreme_dolazna, posecen, dolazna, lowlink, roditelj, mostovi, listaSuseda);
            
            // 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);
         }
   }
}


int main() {

   int n, m;
   cin >> n >> m;

   vector<vector<int>> listaSuseda(n);

   int u, v;
   for(int i = 0; i < m; i++){
      cin >> u >> v;
      listaSuseda[u-1].push_back(v-1);
      listaSuseda[v-1].push_back(u-1);
   }

   int vreme_dolazna = 0;
   vector<bool> posecen(n);
   vector<int> dolazna(n);
   vector<int> lowlink(n);
   vector<int> roditelj(n);

   vector<pair<int,int>> mostovi;

   // određujemo sve mostove grafa
   dfs_mostovi(0, vreme_dolazna, posecen, dolazna, lowlink, roditelj, mostovi, listaSuseda);

   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;
}