Deux sommets sont-ils accessibles dans un graphe ?
On vous donne un graphe non orienté avec
v sommets et e arêtes. Vous avez q requêtes pour déterminer si deux sommets sont accessibles : en d'autres termes, s’il est possible de passer de l’un à l’autre en parcourant le graphe.Entrée
La première ligne de l’entrée contient deux entiers
v (1 ≤ v ≤ 1000) et e (1 ≤ e ≤ 1000).Chacune des
e lignes suivantes contient une paire d’entiers v1, v2 (1 ≤ v1, v2 ≤ v) indiquant que le sommet v1 est connecté au sommet v2 et inversement.La ligne suivante contient un seul entier
q (1 ≤ q ≤ 100), le nombre de requêtes.Chacune des
q lignes contient une paire d’entiers q1, q2 (1 ≤ q1, q2 ≤ v), qui sont les sommets sur lesquels portent les requêtes.Sortie
Pour chacune des requêtes, le programme doit afficher
Yes si le sommet q1 est accessible depuis q2 (et inversement), ou No dans le cas contraire.Exemples
Entrée | Sortie |
7 6
1 2
2 3
1 3
4 5
5 6
4 6
4
1 2
2 5
3 6
4 6 | Yes
No
No
Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB