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șem
– numărul de perechi de orașe între care există șosea unidirecționalăk
– numărul de orașe sigurev
– 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șulp
sau orașulq
sunt nesigure. Este important să fie sigure orașele intermediare. - O pereche
p q
poate fi aleasă dacă există șosea de lap
laq
.
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
#include <bits/stdc++.h> using namespace std; int n , m , s , x , y , v[101] , d[101] , p , cnt , sg[101] , k , vi , q , rez[1001]; vector <int> G[101]; void bfs(int s , int q) { queue <int>Q; Q.push(s); v[s] = 1; d[s] = 1; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i : G[x]) if(!v[i] && (sg[i] || i == q)) { d[i] = d[x] + 1; Q.push(i); v[i] = 1; } } } int main() { cin >> n >> m >> k >> vi; for(int i = 1 ; i <= m ; i++) { cin >> x >> y; G[x].push_back(y); } for(int i = 1 ; i <= k ; i++) { cin >> x; sg[x] = 1; } for(int i = 1 ; i <= vi ; i++) { for(int j = 1 ; j <= n ; j++) d[j] = v[j] = 0; cin >> p >> q; bfs(p , q); if(v[q] > 0) rez[++cnt] = 1; else rez[++cnt] = 0; } for(int i = 1 ; i <= cnt; i++) if(rez[i] == 1) cout << "DA" << '\n'; else cout << "NU" << '\n'; }