Opis glavnog rešenja

Neusmeren graf je bipovezan ako i samo ako je povezan i nema artikulacionih tačaka. Zato se zadatak svodi na dve provere:

• da li su svi čvorovi dostižni iz nekog početnog čvora;
• da li u grafu postoji artikulaciona tačka.

Obe provere možemo uraditi jednim obilaskom u dubinu. Tokom DFS-a za svaki čvor pamtimo vreme prvog obilaska tin i vrednost low. Vrednost low[u] predstavlja najmanje vreme obilaska nekog čvora do kog se može stići iz poddrveta čvora u, koristeći eventualno jednu povratnu granu.

Tokom obilaska koristimo standardne uslove za artikulacione tačke:

• ako je čvor koren DFS drveta i ima bar dva deteta, onda je artikulaciona tačka;
• ako čvor nije koren i postoji njegovo dete v takvo da je low[v] >= tin[u], onda je taj čvor artikulaciona tačka.

Nakon DFS-a proverimo da li postoji neposećen čvor. Ako postoji, graf nije povezan i samim tim nije bipovezan. Ako su svi čvorovi posećeni, a pritom nije pronađena nijedna artikulaciona tačka, graf jeste bipovezan.

Složenost algoritma je \(O(n + m)\), jer se svaki čvor i svaka grana obrađuju konstantan broj puta.

#include <iostream>
#include <vector>

using namespace std;

class Graph {
private:
   int broj_cvorova;
   vector<vector<int>> lista_suseda;
   vector<bool> posecen;
   vector<int> roditelj;
   vector<int> dolazna;
   vector<int> lowlink;
   int vreme;
   bool ima_artikulacionu_tacku;

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

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

   void DFS(int cvor) {
      posecen[cvor] = true;
      dolazna[cvor] = vreme;
      lowlink[cvor] = vreme;
      vreme++;

      int broj_dece = 0;

      for (int sused : lista_suseda[cvor]) {
         if (!posecen[sused]) {
            roditelj[sused] = cvor;
            DFS(sused);
            broj_dece++;

            if (lowlink[sused] < lowlink[cvor]) {
               lowlink[cvor] = lowlink[sused];
            }

            if (roditelj[cvor] == -1 && broj_dece > 1) {
               ima_artikulacionu_tacku = true;
            }

            if (roditelj[cvor] != -1 && lowlink[sused] >= dolazna[cvor]) {
               ima_artikulacionu_tacku = true;
            }
         }
         else if (sused != roditelj[cvor]) {
            if (dolazna[sused] < lowlink[cvor]) {
               lowlink[cvor] = dolazna[sused];
            }
         }
      }
   }

   bool bipovezan() {
      if (broj_cvorova == 0) {
         return true;
      }

      DFS(0);

      for (int i = 0; i < broj_cvorova; i++) {
         if (!posecen[i]) {
            return false;
         }
      }

      return !ima_artikulacionu_tacku;
   }
};

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);
   }

   if (G->bipovezan()) {
      cout << "Da\n";
   }
   else {
      cout << "Ne\n";
   }

   delete G;
   return 0;
}