Usmeri grane!

Neka je dat aciklički graf koji ima i usmerene i neusmerene grane. Potrebno je sve neusmerene grane usmeriti tako da graf i dalje ostane aciklički.

Opis ulaza

Sa standardnog ulaza se unosi broj čvorova u grafu \(n\). Nakon toga se unose vrednosti \(m\) i \(p\) koje predstavljaju broj usmerenih i neusmerenih grana redom. Zatim se unose prvo usmerene a onda i neusmerene grane koje su određene sa po 2 čvora.

Opis izlaza

Na standardni izlaz ispisati grane grafa koje su usmerene primenom odgovarajućeg algoritma.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Za rešavanje zadatka možemo iskoristiti topološko sortiranje. Ovaj algoritam je moguće primeniti samo nad acikličkim usmerenim grafovima. Iz tog razloga ćemo formirati graf koji sadrži samo usmerene grane. Neusmerene ćemo zapamtiti kako bismo mogli da ih kasnije usmerimo. Nakon primene algoritma topološkog sortiranja dobićemo topološki poredak u grafu. Možemo primetiti da su sve grane usmerene od čvorova koji su ranije u topološkom poretku ka čvorovima koji se nalaze kasnije u topološkom poretku. Ovu činjenicu možemo iskoristiti i sve grane koje je potrebno usmeriti možemo usmeriti od čvora koji je ranije u topološkom poretku ka čvoru koji je kasnije u tom poretku. Na ovaj način graf ostaje aciklički jer nema nijedne grane koja nas “vraća” ka nekom ranijem čvoru i time formira ciklus. Kako je glavni deo rešenja algoritam topološkog sortiranja, vremenska složenost je jednaka složenosti ovog algoritma, odnosno \(O(n + m)\).

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {

private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;
   // Vektor koji cuva ulazne stepene za svaki od cvorova
   vector<int> ulazni_stepeni;
   // Vektor koji cuva poziciju svakog cvora u topoloskom sortiranju
   vector<int> pozicija_u_topoloskom_poretku;
   vector<pair<int, int>> neusmerene_grane;
   // Vektor grana koje smo dodali (usmerili neusmerene)
   vector<pair<int, int>> dodate_grane;

public:
   Graph(int broj_cvorova) {
      this->broj_cvorova = broj_cvorova;
      lista_suseda.resize(broj_cvorova);
      ulazni_stepeni.resize(broj_cvorova, 0);
      pozicija_u_topoloskom_poretku.resize(broj_cvorova, -1);
   }

   void dodaj_usmerenu_granu(int u, int v) {
      lista_suseda[u].push_back(v);
      // Uvecavamo ulazni stepen cvora v jer je grana usmerena od u ka v
      ulazni_stepeni[v]++;
   }

   // Granu ne dodajemo stvarno u graf, vec pamtimo da je potrebno da postoji.
   // Kada odredimo kako ona treba da bude usmerena, dodacemo je u graf
   void dodaj_neusmerenu_granu(int u, int v) {
      neusmerene_grane.push_back({ u, v });
   }

   // Kanov algoritam za topolosko sortiranje
   void topolosko_sortiranje() {
      queue<int> cvorovi;

      for (int i = 0; i < broj_cvorova; i++) {
         if (!ulazni_stepeni[i]) {
            cvorovi.push(i);
         }
      }

      int cvor;

      // Cvor koji je prvi u topoloskom sortiranju imati vrednost 0, a onda ce se vrednost za ostale uvecavati
      int position_in_topological_sort = 0;

      while (!cvorovi.empty()) {
         cvor = cvorovi.front();
         cvorovi.pop();

         // Postavljamo poziciju cvora u topoloskom sortiranju na odgovarajucu vrednost
         pozicija_u_topoloskom_poretku[cvor] = position_in_topological_sort++;

         // Prolazimo kroz sve cvorove koji su susedni cvoru cvor, smanjujemo im ulazni stepen, i onda ako je neki dosao do ulaznog stepena 0,
         // znaci da smo zavrsili sve aktivnosti od kojih on zavisi, tako da se i on moze dodati na kraj reda
         for (int sused : lista_suseda[cvor]) {
            ulazni_stepeni[sused]--;

            if (ulazni_stepeni[sused] == 0) {
               cvorovi.push(sused);
            }
         }
      }
   }

   void usmeri_grane() {
      topolosko_sortiranje();

      for (auto &[u, v] : neusmerene_grane) {
         // Ako je u pre v u topoloskom redosledu dodajemo granu u -> v
         if (pozicija_u_topoloskom_poretku[u] < pozicija_u_topoloskom_poretku[v]) {
            dodaj_usmerenu_granu(u, v);
            dodate_grane.push_back({u, v});
         }
         // Inace dodajemo granu v -> u
         else {
            dodaj_usmerenu_granu(v, u);
            dodate_grane.push_back({v, u});
         }
      }

      for (auto &[u, v] : dodate_grane) {
         cout << u << " " << v << endl;
      }
   }
};

int main ()
{
   int n, m, p;
   cin >> n >> m >> p;

   Graph *G = new Graph(n);

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

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

   G->usmeri_grane();
   return 0;
}