Problema berarii2 – infoarena.ro

Berarii2
Berila s-a decis sa se mute in vara asta intr-un oras nou, cu multe plaje frumoase. Berila a studiat planul orasului si a selectat N intersectii in care ar putea sta, M starzi unidirectionale intre acestea precum si P berarii aflate in aceste intersectii. Dupa ce a analizat atent harta Berila a reazlizat ca exista intersectii din care nu poate ajunge la nici una din berariile agreate, acest lucru i se pare lui Berila inacceptabil, asa ca va roaga pe voi sa-i gasiti lista de intersectii din care nu poate ajunge la nici o berarie.

Sursa: Berarii2 – infoarena.ro

Problema acesta pare dificila la inceput, dar daca analizam cuvintele cheie din ea, putem sa o rezolvam mai usor. Stim ca:

• exista N intersectii
• M strazi unidirectionale (adica poti ajunge din punctul A in punctul B, dar nu si invers)
• P berarii ce se pot afla in cele N intersectii
• Berila nu poate ajunge la anumite berarii – asa ca doreste sa afle unde nu poate ajunge

Pentru ca este vorba despre mai multe puncte de interes, cat si o cale de a ajunge de la un punct de interes la altul, problema aceasta este una in care ne vom folosii de Teoria Grafurilor

Am stabilit deci ca vom folosii grafurile pentru a rezolva problema, urmatorul pas fiind sa identificam cine sunt punctele de interes si care sunt legaturile. Stim ca avem mai multe intersectii in care se afla punctul nostru de interes (beraria). Deoarece beneficiem de un drum de la o intersectia la alta, ajungem la concluzia ca intersectiile reprezinta nodurile iar strazile unidirectionale reprezinta muchiile dintr-un graf orientat.

Exemplu

Haideti atunci sa facem desenul aferent exemplului de intrare.

Deseneul aferent problemei. Click pe el pentru zoom

Nodurile speciale (cele in care se afla berarii), sunt marcate cu verde. Dintr-o privire rapida asupra desenului, putem vedea ca din nodul 2 nu putem ajunge la nici o berarie.
De asemenea, daca luam fiecare nod la rand, vedem ca nici din nodul 3, nu avem nici o cale de a ajunge la o berarie. Prin urmare, raspunsul acestei probleme este:

2
2 3

Algoritmul problemei

Avem doua metode pentru a rezolva problema. Putem sa abordam problema printr-o parcurgere in latime (BFS) sau printr-o parcurgere in adancime (DFS). Vom alege Parcurgerea in Adancime (DFS) deoarece este mult mai usor de inteles.

Acum, trebuie sa observam urmatoarea idee: daca putem ajunge dintr-un punct la o berarie, inseamna ca putem ajunge si de la berarie, la acel punct. Cu alte cuvinte: in loc sa parcurgem fiecare nod in adancime, si sa vedem daca ajungem la o berarie, vom aborda problema invers: vom lua fiecare berarie in parte si vom vedea daca putem ajunge la toate punctele sau nu. In momentul in care am pornit cate un algoritm DFS din fiecare berarie, verificam la final numarul berarilor la care nu am putut ajunge.

Observatie: deoarece abordam problema in mod invers, vom retine si drumurile in mod invers. Cum? In loc sa memoram drumul (1, 3), vom memora drumul (3, 1) – pentru ca pornim de la berarie.

Pentru cei ce nu inteleg liniile de mai jos, trebuie sa se uite peste tutorialul algoritmului DFS.

#include    <fstream>
#include    <vector>

#define NLIM 1000005

using namespace std;

ifstream fin("berarii2.in");
ofstream fout("berarii2.out");

int N, M, P;
vector < int > Beers, Edges[NLIM], answers;
bool beenThere[NLIM];

void Read()
{
    int x, y;
    fin >> N >> M >> P; //Citim numarul total al intersectiilor, drumurilor si berariilor
    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y; //Citim drumul x -> y
        Edges[y].push_back(x); //Retinem drumul invers (y -> x)
    }
    for(int i = 1; i <= P; i++)
    {
        fin >> x; //Citim numarul total al berariilor
        Beers.push_back(x); //Le plasam in vectorul "Beers"
    }
}

void DFS(int node)
{ //Algoritmul DFS
    beenThere[node] = true;
    for(unsigned int i = 0; i < Edges[node].size(); i++)
    {
        if(!beenThere[Edges[node][i]])
            DFS(Edges[node][i]);
    }
}

void Solve()
{
    for(unsigned int i = 0; i < Beers.size(); i++)
    {//Luam fiecare berarie la rand si pornim cate un DFS
        if(!beenThere[Beers[i]])
            DFS(Beers[i]);
    }
    for(int i = 1; i <= N; i++)
    {//Parcurgem toate nodurile si vedem unde nu am putut ajunge
        if(beenThere[i] == false)
            answers.push_back(i); //Plasam o intersectie izolata in vectorul "answers"
    }

    fout << answers.size() << "\n"; //Afisam dimensiunea totala a vectorului "answer"
    for(unsigned int i = 0; i < answers.size(); i++)
        fout << answers[i] << "\n"; //Afisam fiecare intersectie in care nu am putut ajunge
}

int main()
{
    Read();
    Solve();
    return 0;
}

Daca aveti intrebari sau nelamuriri, va astept cu un mesaj pe pagina noastra de Facebook: Tutoriale-Pe.NET