Cerința

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

Date de intrare

Fișierul de intrare epidemie.in conține pe prima linie numerele n m, reprezentând numărul persoanelor și numărul perechilor de persoane care se cunosc reciproc. Urmează m linii cu câte două numere i j, cu semnificația: persoanele i și j se cunosc. Pe următoarea linie se află numărul k de persoane infectate inițial, iar pe ultima linie se află k numere distincte cuprinse între 1 și n, reprezentând aceste persoane.

Date de ieșire

Fișierul de ieșire epidemie.out va conține pe prima linie numărul Z, reprezentând numărul de zile după care toate cele n persoane sunt infectate.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ m ≤ n*(n-1)/2
1 ≤ i , j ≤ n
1 ≤ k ≤ n
ziua inițială va fi luată în considerare
graful asociat acestei populații este conex

Exemplu

epidemie.in

epidemie.out

Explicație

În prima zi se îmbolnăvesc persoanele: 4 8. În ziua a doua se infectează 2 3 5 7 10. În ziua a treia se infectează 1 6 9.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Epidemie:

#include <iostream>
#include <fstream>
using namespace std;

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

int n , a[1005][1005];
int x[1005], // coada pentru parcurgerea in latime
    v[1005], // vector caracteristic care precizeaza daca un varf a fost sau nu vizitat
    d[1005]; // distantele la varfuri
int st, dr;

int main()
{
    int i , j, m, k , p;
    fin >> n >> m;
    while( m )
    {
        fin >> i >> j;
        a[i][j] = a[j][i] = 1;
        m --;
    }
    fin >> k;
    for( ; k ; --k)
    {
        fin >> p;
        x[++dr] = p;
        v[p] = d[p] = 1;
    }
    st = 1;
    while(st <= dr)
    {
        int k = x[st];
        for(int i = 1; i <= n ; ++i)
            if(v[i] == 0 && a[k][i] == 1)
            {
                dr ++;
                v[i] = 1;
                x[dr] = i;
                d[i] = d[k] + 1;
            }
        st ++;
    }
    int C = 0;
    for(int i = 1 ; i <= n ; ++i)
        if(d[i] > C)
            C = d[i];
    fout << C;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #549 Epidemie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #549 Epidemie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #549 Epidemie