Grafs amb colors

Tenim un graf dirigit amb n vèrtexs i m arcs, on cada vèrtex té un
color. Es vol saber si hi ha un camí dirigit entre parells de vèrtexs
donats de manera que, al llarg del camí, no hi hagi dos vèrtexs
consecutius amb el mateix color.

Entrada

L’entrada comença amb el valor de n i després n parells, cadascuna amb
el nom d’un vèrtex i el seu color (dues paraules, separades per un
espai). Després ve el valor de m i els m arcs, formats per dos noms de
vèrtexs, sense repeticions ni auto-bucles. Finalment ve una seqüència de
parell de vèrtexs x, y. Podeu suposar que tots els x i y són vèrtexs del
graf.

Sortida

Per cada parell de vèrtexs x, y de la seqüència, escriviu “yes” o “no”
depenent de si hi ha o no un camí de x a y sense dos vèrtexs consecutius
del mateix color.

Informació del problema

Autoria: Jordi Petit

Generació: 2026-03-18T07:28:45.417Z

© Jutge.org, 2006–2026.
https://jutge.org
