Camí màxim P38244


Statement
 

pdf   zip

thehtml

Donat un graf no dirigit, calculeu-ne el camí més llarg, amb una restricció: des de cada vèrtex x només us podeu moure als vèrtexs adjacents y tals que y > x.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y descrivint una aresta entre x i y, amb xy. Suposeu 1 ≤ n ≤ 105, 0 ≤ m ≤ 5n, que els vèrtexs es numeren a partir de 0, i que no hi ha més d’una aresta entre cada parell x y.

Sortida

Per a cada graf, primer escriviu la longitud del camí més llarg (mesurat com el nombre de vèrtexs). A continuació, escriviu ‘:’, i els vèrtexs d’aquest camí separats amb espais. En cas d’empat, trieu el camí lexicogràficament més gran.

Public test cases
  • Input

    9 5   0 5  4 1  5 6  3 2  4 8
    3 0
    7 8   1 4  2 5  6 4  4 3  1 0  0 2  5 1  4 2
    

    Output

    3 : 1 4 8
    1 : 2
    4 : 0 2 4 6
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++