# PBinfo #585 – Orase – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

5 6 3 4
1 2
1 4
2 3
2 4
4 3
3 5
2 3 5
1 5
2 5
6 4
6 5
Ieșire

DA
DA
NU
NU

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/585)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/585/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-585/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)