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 <= \(n\), \(m\) <= 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 izlaz ispisati, svaki u svom redu, odgovore na upite. 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 nakon razmaka 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;

int vreme_dolazna = 0;
vector<bool> posecen;
vector<int> dolazna;
vector<int> lowlink;
vector<int> roditelj;
vector<bool> artikulacioneTacke;
vector<vector<int>> listaSuseda;

void dfs_artikulacione(int cvor) {
   // dodeljujemo redni broj cvoru 'cvor'
   posecen[cvor] = true;
   dolazna[cvor] = vreme_dolazna ++;
   // broj dece cvora cvor
   int broj_dece = 0;
   // vrednost funkcije L za cvor 'cvor' inicijalizujemo na njegov redni broj
   lowlink[cvor] = dolazna[cvor];
   // rekurzivno prolazimo kroz sve susede koje nismo obisli
   for (auto sused : listaSuseda[cvor]) {
      // ako je grana (cvor, sused) povratna i ne vodi ka roditelju cvora 'cvor'
      if (posecen[sused]) {
         if (sused != roditelj[cvor])
            // po potrebi azuriramo vrednost L za cvor 'cvor'
            if (dolazna[sused] < lowlink[cvor])
               lowlink[cvor] = dolazna[sused];
      } else {
         // 'sused' je novo dete cvora 'cvor' u DFS drvetu
         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 L
         // cvora 'sused' je odredjena, pa po potrebi azuriramo vrednost L 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])
            artikulacioneTacke[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
      artikulacioneTacke[cvor] = true;
}


int main() {

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

   listaSuseda.resize(n);
   posecen.resize(n, false);
   dolazna.resize(n);
   lowlink.resize(n);
   roditelj.resize(n, -1);
   
   artikulacioneTacke.resize(n, false);

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

   for(int i = 0; i < n; i++)
      if(!posecen[i])
         dfs_artikulacione(i);

   int q, ind;
   cin >> q;
   while(q--){
      cin >> ind;
      if(artikulacioneTacke[ind]){
         cout << "Da " << listaSuseda[ind].size() << endl;
      } else {
         cout << "Ne" << endl;
      }
   }

   return 0;
}