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 \leq n \leq 10^5\)), a zatim broj dvosmernih puteva između njih \(m\) (\(1 \leq m \leq 10^5\)). U narednih \(m\) linija nalaze se po dva različita broja \(a_i\) i \(b_i\) (\(1 \leq a_i, b_i \leq n, a_i \neq 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, prepoznati korišćenjem niza roditelja.

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
  int broj_cvorova;
  vector<vector<int>> lista_suseda;
  int vreme_dolazna;
  vector<int> dolazna;
  vector<int> lowlink;
  vector<int> roditelj;
  bool postoje_mostovi;

public:
  Graph(int broj_cvorova) {
    this->broj_cvorova = broj_cvorova;
    vreme_dolazna = 0;
    lista_suseda.resize(broj_cvorova);
    dolazna.resize(broj_cvorova, -1);
    roditelj.resize(broj_cvorova, -1);
    lowlink.resize(broj_cvorova);
  }

  void dodaj_granu(int u, int v) {
    // Numeracija cvorova krece od 1, tako da ovde dodajemo granu 2 - 3 umesto grane 3 - 4 na primer
    lista_suseda[u-1].push_back(v-1);
    lista_suseda[v-1].push_back(u-1);
  }

  void dfs_mostovi(int cvor) {
    // dodeljujemo redni broj cvoru 'cvor' i omdah uvecavamo vreme dolazne numeracije za sledeci cvor
    dolazna[cvor] = vreme_dolazna++;
    // inicijalizujemo vrednost lowlinka cvora 'cvor' na njegov redni broj
    lowlink[cvor] = dolazna[cvor];

    // rekurzivno prolazimo kroz sve susede koje nismo obisli
    for (auto sused : lista_suseda[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 lowlinka cvora na redni broj suseda
          if (dolazna[sused] < lowlink[cvor]) {
            lowlink[cvor] = dolazna[sused];
          }
        }
      }
      // ukoliko sused nije posecen
      else {
        // pamtimo granu DFS drveta
        roditelj[sused] = cvor;
        // pokrecemo pretragu iz cvora 'sused'
        dfs_mostovi(sused);

        // nakon obrade poddrveta čiji je koren cvor 'sused' vrednost lowlinka cvora 'sused' je odredjena
        // po potrebi azuriramo vrednost lowlinka 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 lowlinka cvora 'sused' i rednog broja cvora 'cvor' odredjene
        if (lowlink[sused] > dolazna[cvor]) {
          postoje_mostovi = true;
        }
      }
    }
  }

  bool ima_mostove() {
    return postoje_mostovi;
  }

  void usmeri_grane() {
    for (int cvor = 0; cvor < broj_cvorova; cvor++)
      for (int sused : lista_suseda[cvor]) {
        // u neusmerenom grafu je svaka grana predstavljena dva puta
        // ovim se obezbeđuje da će se svaka grana razmatrati samo jednom
        // dakle, imamo grane 0 -> 1 i 1 -> 0 kada predstavljamo neusmereni graf
        // kako ne bismo "usmeravali" obe grane, razmatramo samo granu od 0 ka 1
        // i za nju proveravamo da li je grana drveta ili povratna grana
        if (cvor > sused) {
          continue;
        }

        // (u, v) je ta grana usmerena od pretka ka potomku
        int u = cvor, v = sused;
        // zelimo da uvek razmatramo granu koja vodi od u ka v. ako je dolazna
        // numeracija cvora u veca od dolazne numeracije cvora v, to znaci da je grana
        // usmerena suprotno od onoga sto zelimo, tako da samo menjamo u i v
        if (dolazna[u] > dolazna[v]) {
          swap(u, v);
        }

        // usmeravamo granu na pravi način
        if (roditelj[v] == u) {
          // grana drveta
          // po tekstu zadatka, cvorovi su numerisani od 1 do n a kod nas u kodu je numeracija od
          // o do n - 1
          cout << u+1 << " " << v+1 << endl;
        }
        else {
          // povratna grana
          cout << v+1 << " " << u+1 << endl;
        }
      }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;

  Graph *G = new Graph(n);

  int m, u, v;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    G->dodaj_granu(u, v);
  }

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

  if (G->ima_mostove())
    // 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"
    G->usmeri_grane();
  }

  return 0;
}