Svetiljke

U kraljevom vrtu postoje svetiljke koje se svako veče pale tako da osvetle ceo vrt. Svetiljke imaju senzore koji omogućavaju da se data svetiljka upali ukoliko detektuju da je svetiljka u blizini upaljena.

Jedan od kraljevih podanika je zadužen za paljenje svetiljki svako veče. Potrebno je napisati program koji određuje koliko minimalno svetiljki on mora ručno da upali da bi se sve svetiljke u vrtu upalile.

Opis ulaza

Sa standardnog ulaza se učitavaju dva cela broja \(n\) i \(m\) (\(1 \leq n \leq 100\)), koji redom predstavljaju broj svetiljki i broj senzora u vrtu. Nakon toga se u sledećih \(m\) linija zadaju senzori na sledeći način:

Opis izlaza

Ispisati minimalan broj svetiljki koje je potrebno ručno upaliti da i se osvetlio ceo vrt.

Primer 1

Ulaz

Izlaz

Primer 2

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Svetiljke možemo predstaviti čvorovima, a senzore granama, pri čemu ćemo grane usmeravati od svetiljke koja aktivira senzor ka svetiljci koja ima senzor i pali se.

U slučaju da graf nema ciklusa, problem je relativno jednostavan. Potrebno je i dovoljno upaliti one svetiljke koje nemaju ni jedan senzor. Ovim će se upaliti sve svetiljke u vrtu, jer ukoliko za proizvoljan čvor koji ima bar jedan senzor pratimo grane u nazad, u nekom trenutku ćemo naići na neki čvor koji ima ulazni stepen 0, odnosno nema senzor (ovo važi jer nemamo cikluse, pa se možemo “vrteti u krug” vraćajući se kroz grane). Dakle, dovoljno je izbrojati čvorove sa ulaznim stepenom 0.

U slučaju da postoje ciklusi, rešenje je nešto komplikovanije. Primetimo da je za svaku komponentu jake povezanosti dovoljno upaliti jednu svetiljku i sve ostale u okviru te komponente će se upaliti. Zbog ovoga, možemo posmatrati svaku komponentu kao jednu svetiljku koju treba upaliti, pa možemo formirati kondenzovani graf u kome su komponente jake povezanosti čvorovi, a grane između njih postoje ukoliko postoji barem jedna grana od nekog čvora jedne komponente do nekog čvora druge. Sada se problem svodi na onaj opisan u prethodnom pasusu, pošto je kondenzovani graf acikličan.

#include <iostream>
#include <vector>
#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;
  stack<int> odlazna_enumeracija;
  vector<int> komponente;
  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 nadji_komponente() {
    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++;
      }
    }
  }

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

  int nadji_broj_prekidaca(){

   nadji_komponente();

   vector<int> niz_komponenti(broj_komponente, 0);

   for(int i = 0; i < broj_cvorova; i++){
      for(auto j : lista_suseda[i]){
         if(komponente[i] != komponente[j])
            niz_komponenti[komponente[j]]++;
      }
   }

   int rezultat = 0;

   for(int i = 0; i < broj_komponente; i++)
      if(niz_komponenti[i] == 0)
         rezultat++;

   return rezultat;
  }
};

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-1, v-1); 
   }

   cout << G->nadji_broj_prekidaca() << endl;

   delete G;
   
   return 0;
}