Nombre de cicles P62130


Statement
 

pdf   zip

thehtml

Donat un graf no dirigit i connex, compteu-ne el nombre de cicles. Recordeu que un cicle és un camí que comença i acaba al mateix vèrtex, i que no té cap altre vèrtex repetit. Amb els grafs no dirigits, aquest camí ha de tenir almenys tres arestes.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y indicant una aresta entre x i y. Suposeu 3 ≤ n ≤ 11, que els vèrtexs es numeren començant en 0, i que no hi ha més d’una aresta entre dos vèrtexs.

Sortida

Per a cada graf, escriviu el seu nombre de cicles.

Pista

Considereu comptar, per a cada vèrtex x, quants cicles comencen en x i no passen per cap vèrtex més petit que x.

Public test cases

  • Input

    3 2
0 1  0 2

3 3
0 1  1 2  2 0

4 4
0 1  1 2  2 3  3 0

4 5
0 1  2 0  1 2  2 3  3 0

    Output

    0
1
1
3
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++