Raskrsnice

U gradu postoji \(n\) raskrsnica povezanih jednosmernim i dvosmernim ulicama. Kako je grad moderan, neke od ulica imaju nadvožnjake. Potrebno je obezbediti da svake dve raskrsnice budu povezane. Preciznije, za svake dve raskrsnice \(v\) i \(w\) mora da važi da je iz \(v\) moguće doći u \(w\) i da je iz \(w\) moguće doći u \(v\). Potrebno je napisati program koji učitava opise puteva u gradovima i ispisuje za koje gradove je zadovoljen uslov povezanosti.

Opis ulaza

Sa standardnog ulaza se učitava broj upita \(q\), a zatim i sami upiti. Svaki upit ima u prvoj liniji dva cela broja \(n\) i \(m\) (\(1 \leq n \leq 100\)), koji redom predstavljaju broj raskrsnica i broj ulica u datom gradu. Nakon toga se u sledećih \(m\) linija zadaju ulice na sledeći način:

Opis izlaza

Na standardni izlaz za svaki od upita ispisati Da ukoliko je uslov povezanosti svaka dva čvora ispunjen, a Ne u suprotnom.

Primer

Ulaz

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

Izlaz

Da
Da
Ne
Ne

Rešenje

Opis glavnog rešenja

Zadatak se svodi na proveru da li je graf jako povezan. Koristimo Kosarajuov algoritam koji se oslanja na činjenicu da ukoliko obrnemo grane u grafu, sastav komponenti jake povezanosti ostaje isti. Sastoji se iz sledećih koraka:

  1. Pokrenuti DFS iz proizvoljnog početnog čvora. Ukoliko nakon toga postoji neki neposećen čvor, zaključujemo da graf nije jako povezan, pošto taj čvor i početni čvor ne mogu biti u istoj komponenti.

  2. Pokrenuti ponovo DFS iz istog početnog čvora, ali za graf sa obrnutim granama. Ukoliko sada postoji neki neposećen čvor, ponovo taj čvor i početni čvor ne mogu biti u istoj komponenti na osnovu pretpostavke algoritma, pa zaključujemo da graf nije jako povezan. U suprotnom graf jeste jako povezan.

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

using namespace std;

class Graph {
private:
  int broj_cvorova;
  vector<vector<int>> lista_suseda;
  vector<vector<int>> obrnuta_lista_suseda;
  vector<bool> posecen;

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

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

  void dfs1(int koren) {

    stack<int> s;
    s.push(koren);
    posecen[koren] = true;

    int trenutni;
    while (!s.empty()) {
      trenutni = s.top();
      s.pop();

      for (int neighbour : lista_suseda[trenutni])
        if (!posecen[neighbour]) {
          s.push(neighbour);
          posecen[neighbour] = true;
        }
    }

  }

    void dfs2(int koren) {

    stack<int> s;
    s.push(koren);
    posecen[koren] = true;

    int trenutni;
    while (!s.empty()) {
      trenutni = s.top();
      s.pop();

      for (int neighbour : obrnuta_lista_suseda[trenutni])
        if (!posecen[neighbour]) {
          s.push(neighbour);
          posecen[neighbour] = true;
        }
    }

  }

  bool kosaraju(int koren){

   dfs1(koren);

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

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

   dfs2(koren);

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

   return true;
  }
};

int main() {

   int q;
   cin >> q;

   while(q--){

      int broj_cvorova, number_of_edges;
      cin >> broj_cvorova >> number_of_edges;

      Graph *G = new Graph(broj_cvorova);

      int u, v, je_usmeren;
      for (int i = 0; i < number_of_edges; i++) {
         cin >> je_usmeren >> u >> v;
         if(je_usmeren == 1)
            G->dodaj_granu(true, u-1, v-1);
         else
            G->dodaj_granu(false, u-1, v-1);   
      }

      if(G->kosaraju(0))
         cout << "Da" << endl;
      else
         cout << "Ne" << endl;

      delete G;
   }
  return 0;
}