Cerința

Într-o țară oarecare sunt n orașe, numerotate de la 1 la n, între care există șosele unidirecționale. Președintele țării vrea să facă o vizită electorală prin mai multe orașe în felul următor: aterizează cu elicopterul în orașul p, merge până în orașul q folosind rețeaua de șosele existentă, de unde pleacă cu elicopterul. Din punct de vedere politic unele orașe sunt sigure (conduse de aliați politici ai președintelui), altele sunt nesigure (conduse de adversari), iar președintele dorește să parcurgă numai orașe sigure.

Consilierii președintelui i-au propus mai multe perechi de orașe p q care pot fi alese ca punct de plecare și de sosire pentru vizită. Președintele vă cere să verificați pentru fiecare pereche dată dacă există un drum care să treacă numai prin orașe sigure.

Date de intrare

Programul citește de la tastatură numerele n m k v, reprezentând:

n – numărul total de orașe
m – numărul de perechi de orașe între care există șosea unidirecțională
k – numărul de orașe sigure
v – numărul de perechi de orașe propuse pentru vizită

Programul va citi apoi m perechi de orașe i j, cu semnificația că există șosea unidirecțională de la orașul i la orașul j. Apoi se vor citi cele k orașe sigure, apoi cele v perechi de orașe candidat p q.

Date de ieșire

Programul va afișa pe ecran pe v linii mesajul DA sau NU, după cum perechea corespunzătoare de orașe candidat poate fi aleasă pentru vizită, sau nu.

Restricții și precizări

1 ≤ k ≤ n ≤ 100
O pereche p q poate fi aleasă chiar dacă orașul p sau orașul q sunt nesigure. Este important să fie sigure orașele intermediare.
O pereche p q poate fi aleasă dacă există șosea de la p la q.

Exemplu

Intrare

Ieșire

DA
DA
NU
NU

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 Orase:

#include <iostream>

using namespace std;


int n , a[105][105], s[105];

int main()
{
    int m , kk , v , p , q;
    cin >> n >> m >> kk >> v;
    while( m )
    {
        int i , j;
        cin >> i >> j;
        a[i][j] = 1;
        m --;
    }
    for(int i =1 ; i <= kk ; i ++)
    {
        cin >> p;
        s[p] = 1;
    }
    for(int k = 1 ; k <= n ; ++k)
        if(s[k] == 1)
            for(int i = 1 ; i <= n ; ++i)
                for(int j = 1 ; j <= n ; ++j)
                    if(a[i][j] == 0)
                        a[i][j] = a[i][k] * a[k][j];
    for(int i =1 ; i <= v ; ++i)
    {
        cin >> p  >> q;
        if(a[p][q] == 1)
            cout << "DA
";
        else
            cout << "NU
";
    }
    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 #585 Orase

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #585 Orase 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 #585 Orase