Vèrtexs intermedis X34137


Statement
 

pdf   zip

html

Donats un graf dirigit i dos vèrtexs u i v diferents, calculeu quants vèrtexs x que no siguin ni u ni v hi ha tals que existeix algun camí d’u a v que passa per x.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, u, v i m, seguit d’m parells diferents x y, amb x ≠ y, que indiquen un arc que va d’x a y. Suposeu 2 ≤ n ≤ 104, 0 ≤ m ≤ 10n, i que els vèrtexs es numeren entre 0 i n − 1.

Sortida

Per a cada cas, escriviu la quantitat de vèrtexs pels quals es pot passar anant des d’u fins a v pel camí que sigui.

Pista

Per a cada cas, la solució esperada bàsicament només fa dos recorreguts, cadascun en el graf adequat.

Public test cases

  • Input

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

2 0 1 0

3 0 1 2
1 2
2 0

4 0 2 3
0 2
2 3
3 0

    Output

    3
0
0
1
    • Information
    Author
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++