Uklanjanje cvorova

Neka je dat proizvoljan graf. Potrebno je proveriti da li se broj komponenti povezanosti tog grafa povećava nakon uklanjanja proizvoljnog čvora. Ukoliko je odgovor da, treba odrediti i broj grana koje bi bile obrisane uklanjanjem datog čvora.

Napomena: Nakon uklanjanja čvora, graf se vraća u početno stanje.

Opis ulaza

Sa standardnog ulaza se unose broj čvorova \(n\) i broj grana \(m\) (\(1 \leq n, m \leq 100\)), a zatim i niz parova brojeva od \(0\) do \(n - 1\) koji predstavljaju grane. Nakon toga, unosi se broj upita \(q\), a zatim i \(q\) upita koji označavaju brojeve čvorova koji se uklanjaju.

Opis izlaza

Na standardni izlaz ispisati odgovore na upite, svaki u zasebnom redu. U slučaju da broj komponenti povezanosti ostaje isti, ispisati Ne. U slučaju da se broj komponenti povezanosti uvećava, ispisati Da, a zatim i broj grana obrisanih uklanjanjem datog čvora.

Primer

Ulaz

5 5
0 1
1 2
2 3
3 4
2 4
5
0
1
2
3
4

Izlaz

Ne
Da 2
Da 3
Ne
Ne

Rešenje

Opis glavnog rešenja

Zadatak se svodi na nalaženje svih artikulacionih tačaka u grafu. Ukoliko kao upit dobijemo čvor koji nije artikulaciona tačka, ispisujemo Ne, a u suprotnom ispisujemo Da, kao i dužinu liste susedstva datog čvora, jer ona upravo predstavlja broj grana koje bi bile obrisane njegovim uklanjanjem.

#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;
  vector<bool> artikulacione_tacke;

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);
    artikulacione_tacke.resize(broj_cvorova, false);
  }

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

   void dfs_artikulacione(int cvor) {
      // dodeljujemo redni broj cvoru 'cvor'
      dolazna[cvor] = vreme_dolazna++;

      // broj dece cvora 'cvor'
      int broj_dece = 0;

      // vrednost funkcije lowlink za cvor 'cvor' inicijalizujemo na njegov redni broj
      lowlink[cvor] = dolazna[cvor];

      // rekurzivno prolazimo kroz sve susede koje nismo obisli
      for (auto sused : lista_suseda[cvor]) {
         // ako je grana (cvor, sused) povratna i ne vodi ka roditelju cvora 'cvor'
         if (dolazna[sused] != -1) {
            if (sused != roditelj[cvor])
               // po potrebi azuriramo vrednost lowlinka za cvor 'cvor'
               if (dolazna[sused] < lowlink[cvor]) {
                  lowlink[cvor] = dolazna[sused];
               }
         }
         // 'sused' je novo dete cvora 'cvor' u DFS drvetu
         else {
            broj_dece++;

            // dodajemo granu u DFS drvo
            roditelj[sused] = cvor;

            // pokrecemo pretragu iz cvora 'sused'
            dfs_artikulacione(sused);

            // nakon obrade poddrveta čiji je koren cvor 'sused' vrednost funkcije lowlink
            // cvora 'sused' je odredjena, pa po potrebi azuriramo vrednost lowlinka cvora 'cvor'
            if (lowlink[sused] < lowlink[cvor]) {
               lowlink[cvor] = lowlink[sused];
            }

            // ako 'cvor' nije koren DFS drveta i ako cvor nijedan cvor u poddrvetu cvora 'sused'
            // nije povezan sa nekim pretkom cvora 'cvor' onda je 'cvor' artikulaciona tacka
            if (roditelj[cvor] != -1 && lowlink[sused] >= dolazna[cvor]) {
               artikulacione_tacke[cvor] = true;
            }
         }
      }
      // obradjena su sva deca cvora 'cvor'
      // proveravamo da li je cvor 'cvor' koren DFS drveta i da li ima vise od jednog deteta
      if (roditelj[cvor] == -1 && broj_dece > 1) {
         // ako je uslov ispunjen, cvor je artikulaciona tacka
         artikulacione_tacke[cvor] = true;
      }
   }

   void pronadji_artikulacione_tacke() {
      for(int i = 0; i < broj_cvorova; i++) {
         // Za svaku komponentu povezanosti pokrecemo algoritam i nalazimo artikulacione tacke
         if(dolazna[i] == -1) {
            dfs_artikulacione(i);
         }
      }
   }

   bool da_li_je_artikulaciona_tacka(int cvor) {
      return artikulacione_tacke[cvor];
   }

   int broj_suseda(int cvor) {
      return lista_suseda[cvor].size();
   }

};

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->pronadji_artikulacione_tacke();

   int q, cvor;
   cin >> q;
   while(q--){
      cin >> cvor;
      if(G->da_li_je_artikulaciona_tacka(cvor)){
         cout << "Da " << G->broj_suseda(cvor) << endl;
      } else {
         cout << "Ne" << endl;
      }
   }

   return 0;
}