Graphs (2) P37001


Statement
 

pdf   zip

thehtml

Given a directed graph with n vertices and m arcs, we wish to know if there is a directed path between two given vertices.

Input

Input starts with the value of n and the n names of the vertices. Then comes the value of m and follow the m arcs, made up by the name of two vertices, without repetitions nor autoloops. Then follows a pair of vertices x,y. You can assume that x and y belong to the graph.

Output

Write “yes” o “no” according to whether there is or not a path from x to y.

Public test cases
  • Input

    8
    bcn prs mad rom lsb ber lon dub
    
    10
    bcn prs
    prs mad
    rom lsb
    rom dub
    ber lon
    lsb dub
    dub lsb
    mad lon
    bcn ber
    ber bcn
    
    bcn mad
    

    Output

    yes
    
  • Input

    8
    bcn prs mad rom lsb ber lon dub
    
    10
    bcn prs
    prs mad
    rom lsb
    rom dub
    ber lon
    lsb dub
    dub lsb
    mad lon
    bcn ber
    ber bcn
    
    rom bcn
    

    Output

    no
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python Python
    User solutions
    C++ Python