Polupovezanost

Usmereni graf \(G = (V, E)\) je polupovezan ako, za svaki par različitih čvorova \(u, v \in V\), imamo da je \(u \rightsquigarrow v\) ili \(v \rightsquigarrow u\). Naravno, ukoliko je graf jako povezan, onda je i polupovezan, ali obratno ne mora da važi. Za dati graf odrediti da li je polupovezan.

Opis ulaza

Sa standardnog ulaza se unosi broj čvorova \(n\) (\(1 \leq n \leq 10^4\)), a zatim broj grana \(m\) (\(1 \leq m \leq 10^4\)). Nakon toga, u zasebnim redovima, se unosi niz grana \(u_j, v_j\) (\(0 \leq j < m\)).

Opis izlaza

Na stanadardni izlaz ispisati Da ukoliko je graf polupovezan, inače ispisati Ne.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Rešenje problema se zasniva na sledećem tvrđenju:

Teorema: Neka je dat usmereni aciklični polupovezani graf \(G = (V, E)\), zajedno sa svojim topološkim poretkom \(v_1, \ldots, v_n\). Tada, za svako \(k = 1 \ldots, n - 1\), važi \((v_k, v_{k+1}) \in E\).

Dokaz: Dokaz izvodimo po slučajevima.

Pretpostavimo da za neko \(k = 1, \ldots, n - 1\) ne postoji grana \((v_k, v_{k+1})\). Kako \(v_{k+1}\) dolazi nakon \(v_k\) u topološkom sortiranju znamo da onda ne postoji grana \((v_{k + 1}, v_k)\). Zbog toga ne postoji put \(v_k \rightsquigarrow v_{k+1}\), kao ni put \(v_{k+1} \rightsquigarrow v_k\), te graf \(G\) nije polupovezan.
Ako za svako \(k = 1, \ldots, n - 1\) postoji grana \((v_k, v_{k+1})\), onda, za svako \(i, j = 1, \ldots, n\), pri čemu je \(i < j\), postoji put \(p : v_i \rightsquigarrow v_j\). Preciznije, put \(p\) je oblika \(\langle v_i, v_{i+1}, \ldots, v_{j - 1}, v_j \rangle\). \(\blacksquare\)

Kako se teorema odnosi samo na usmerene aciklične grafove, da bi graf postao acikličan potrebno je sve komponente jake povezanosti originalnog grafa sažeti u jedan čvor. Odavde sledi sledeći algoritam:

Neka su \(C_1, \ldots, C_k\) sve komponente jake povezanosti grafa \(G = (V, E)\).
Definišemo graf \(G^{SCC} = (V^{SCC}, E^{SCC})\), gde svaki čvor \(v_i \in V^{SCC}\) pripada komponenti jake povezanosti \(C_i\), a za svaku usmerenu granu \((v_i, v_j) \in E^{SCC}\) postoji usmerena grana \((x, y) \in E\) za neki \(x \in C_i\) i neki \(y \in C_j\). Graf \(G^{SCC}\) je usmeren i acikličan.
Neka je dalje \(v_1, \ldots, v_k\) topološki poredak čvorova grafa \(G^{SCC}\).
Po prethodnoj teoreme ako za svako \(i = 1 \ldots, k - 1\) važi \((v_i, v_{i+1}) \in E^{SCC}\), onda je \(G^{SCC}\) polupovezan. Tada će i \(G\) biti polupovezan, jer će postojati put između svaka dva čvora unutar jedne komponente jake povezanosti.

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

using namespace std;

class Graph {
private:
    int broj_cvorova;
    vector<vector<int>> lista_suseda;
    vector<vector<int>> obrnuta_lista_suseda;
    vector<vector<int>> lista_suseda_komponente;
    vector<bool> posecen;
    stack<int> odlazna_enumeracija;
    vector<int> komponente;
    vector<int> topoloski_poredak;
    int broj_komponente = 0;

    void dfs1(int v) {
        posecen[v] = true;
        for(int sused : lista_suseda[v]) {
            if(!posecen[sused]) {
                dfs1(sused);
            }
        }
        odlazna_enumeracija.push(v);
    }

    void dfs2(int v, vector<bool>& posecen) {
        posecen[v] = true;
        komponente[v] = broj_komponente;
        for(int sused : obrnuta_lista_suseda[v]) {
            if(!posecen[sused]) {
                dfs2(sused, posecen);
            }
        }
    }

    void komponente_jake_povezanosti() {
        fill(posecen.begin(), posecen.end(), false);
        for(int i = 0; i < broj_cvorova; i++) {
            if(!posecen[i]) {
                dfs1(i);
            }
        }

        fill(posecen.begin(), posecen.end(), false);

        while(!odlazna_enumeracija.empty()) {
            int v = odlazna_enumeracija.top();
            odlazna_enumeracija.pop();
            if(!posecen[v]) {
                dfs2(v, posecen);
                broj_komponente++;
            }
        }
    }

    void DFS_topolosko_sortiranje(int u, stack<int> &s) {
      posecen[u] = true;

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

      // TEK NAKON STO SMO OBILSI 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
      s.push(u);
   }

   void topolosko_sortiranje() {
       fill(posecen.begin(), posecen.end(), false);

       stack<int> s;
       for (int u = 0; u < broj_komponente; u++) {
           if (!posecen[u]) {
               DFS_topolosko_sortiranje(u, s);
           }
       }

       while (!s.empty()) {
           auto u = s.top(); s.pop();

           topoloski_poredak.push_back(u);
       }
   }


    void compress_graph() {
        lista_suseda_komponente = vector<vector<int>>(broj_komponente);

        set<pair<int, int>> ubacene_grane;
        for (int u = 0; u < broj_cvorova; u++) {
            for (auto v : lista_suseda[u]) {
                if (komponente[u] != komponente[v] &&
                    ubacene_grane.count({ komponente[u], komponente[v]}) == 0) {
                    lista_suseda_komponente[komponente[u]].push_back(komponente[v]);
                    ubacene_grane.emplace(komponente[u], komponente[v]);
                }
            }
        }
    }

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

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

    bool je_polupovezan(){
        komponente_jake_povezanosti();

        compress_graph();

        topolosko_sortiranje();
        
        for (int i = 0; i < broj_komponente - 1; i++) {
            auto v_curr = topoloski_poredak[i];
            auto v_next = topoloski_poredak[i + 1];

            bool povezan = false;
            for (auto v : lista_suseda_komponente[v_curr]) {
                if (v == v_next) {
                    povezan = true;
                }
            }
            if (!povezan) {
                return false;
            }
        }

        return true;
    }
};

int main() {
    int N, M, u, v;

    cin >> N >> M;
    Graph *G = new Graph(N);
    for(int i = 0; i < M; i++) {
        cin >> u >> v;
        G->dodaj_granu(u, v); 
    }

    cout << (G->je_polupovezan() ? "Da" : "Ne") << endl;

    delete G;

    return 0;
}