Dodaj grane

Neka je dat usmereni aciklički graf. Potrebno je dodati maksimalan broj grana u ovaj graf tako da on i dalje ostane aciklički.

Opis ulaza

Sa standardnog ulaza se unose vrednosti \(n\) i \(m\) koje predstavljaju broj čvorova i broj grana redom. Nakon toga se u narednih \(m\) linija unose po 2 vrednosti koje predstavljaju grane grafa.

Opis izlaza

Na standardni izlaz ispisati sve grane koje je moguće dodati u graf tako da on i dalje ostane aciklički. Grane ispisati uređene po polaznom čvoru grane.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Za rešavanje ovog zadataka možemo upotrebiti algoritam topološkog sortiranja. Graf je usmeren i aciklički pa je moguće upotrebi ovaj algoritam. Ideja je da za svaki čvor odredimo njegovu pozociju u topološkom poretku. Nakon toga, kako bi graf ostao acikličan, za svaki čvor, dodajemo grane ka svim čvorovima koji su kasnije u topološkom poretku, a grane ka njima već ne postoje iz trenutnog čvora. Kao algoritam topološkog sortiranja koristimo algoritam zasnovan na DFS pretrazi grafa. Kada odredimo poziciju u topološkom poretku za svaki od čvorova, onda možemo da dodamo odgovarajuće grane. Najpre sve čvorove označavamo kao neposećene. Za svaki čvor prolazimo kroz listu njegovih suseda i susede označimo kao posećene (na ovaj način “pamtimo” postojeće grane, odnosno, sprečavamo dodavanje duplih grana ka susedima koji su kasinje u topološkom poretku). Kada “zapamtimo” sve grane koje već postoje u grafu, prođemo redom kroz sve čvorove koji su nakon njega u topološkom poretku i ka svima koji nisu već posećeni (znači da već ne postoji grana u grafu) dodamo grane. Nakon toga sve čvorove opet označimo kao neposećene (jer potencijalno postoje grane od drugih čvorova koje se mogu dodati). Prvi deo algoritma je topološko sortiranje zasnovano na DFS pretrazi čija je složenost \(O(n + m)\). Drugi deo je dodavanje grana u graf. Ovo nije tako trivijalan korak jer je za svaki čvor potrebno proći kroz sve čvorove koji se u topološkom poretku nalaze posle njega. Složenost ovog koraka je kvadratna po broju čvorova odnosno \(O(n^2)\). Nakon određivanja svih grana koje treba dodati potrebno ih je i sortirati. Ova operacija je složenosti \(O(n \log n)\).

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Graph {

private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;
   vector<bool> posecen;
   vector<int> topoloski_poredak;
   vector<pair<int, int>> dodate_grane;
   // Stek koji ce nam je potreban za algoritam topoloskog sortiranja zasnovan na DFS pretrazi grafa
   stack<int> stek;

public:
   Graph(int broj_cvorova) {
      this->broj_cvorova = broj_cvorova;
      lista_suseda.resize(broj_cvorova);
      posecen.resize(broj_cvorova, false);
   }

   void dodaj_granu(int u, int v) {
      lista_suseda[u].push_back(v);
   }

   void DFS_topolosko_sortiranje(int u) {
      posecen[u] = true;

      for (int v : lista_suseda[u]) {
         if (!posecen[v]) {
            DFS_topolosko_sortiranje(v);
         }
      }

      // TEK NAKON STO SMO OBISLI SVE NJEGOVE SUSEDE dodajemo element na stek, kako se on nalazi vise na steku bice i
      // ranije uklonjen sa steka pa ce se naci ranije u topoloskom poretku a svi cvorovi koji "zavise" od njega ce se
      // ukloniti kasnije i samim tim ce se naci kasnije u topoloskom poretku
      stek.push(u);
   }

   void topolosko_sortiranje() {
      for (int i = 0; i < broj_cvorova; i++) {
         if (!posecen[i]) {
            DFS_topolosko_sortiranje(i);
         }
      }

      int cvor;

      while (!stek.empty()) {
         cvor = stek.top();
         stek.pop();

         topoloski_poredak.push_back(cvor);
      }
   }

   void dodaj_grane() {
      topolosko_sortiranje();

      int cvor;
      for (int i = 0; i < broj_cvorova; i++) {
         cvor = topoloski_poredak[i];

         cout << cvor << "\n";

         // Sve cvorove vracamo na neposecene
         fill(posecen.begin(), posecen.end(), false);

         // Pamtimo sve grane koje vec postoje u grafu
         for (int sused : lista_suseda[cvor]) {
            posecen[sused] = true;
         }

         // Dodajemo grane ka svim cvorovima koji su kasnije u topoloskom poretku u odnosu
         // na trenutni cvor, a grana vec ne postoji
         for (int j = i + 1; j < broj_cvorova; j++) {
            int sledeci_cvor = topoloski_poredak[j];
            if (!posecen[sledeci_cvor]) {
               dodate_grane.push_back({cvor, sledeci_cvor});
            }
         }
      }

      sort(dodate_grane.begin(), dodate_grane.end());

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



int main ()
{
   int n, m;

   cin >> n >> m;

   Graph *G = new Graph(n);

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

   G->dodaj_grane();

   return 0;
}