imi pare rau ca dureaza asa mult, am teme in draci. Va trimit rezolvarea, 
testele o sa le fac candva saptamana asta.

rezolvare:

notam cu <pp> pozitia de start a pisicii, cu <ps> pozitia de start a
soarecelui, cu <cs> casa soarecelui si G graful dat pt un input. Construim
urmatoarea matrice indexata dupa nodurile grafului: P[a][b] este 1 daca
pisica are strategie de cashtig daca pleaca din a, si soarecele din b si
urmeaza la mutare, 0 altfel. tabela se initializeaza in urmatorul mod:

P[a][b] = 1 daca a==b!=cs

repeta urmatorul pas de n^2 ori: pt orice pereche de noduri (a,b) in VxV,
seteaza P[pos_pisica][pos_soarice] la 1 daca exista o mutare a pisicii 
astfel incat:

1) (pos_pisica' != cs) si (pos_pisica'==pos_soarice) sau
2) (pos_soarice!=cs) si pt toate mutarile soaricelui 
P[pos_pisica'][pos_soarice'] == 1

dupa n^2 iteratii, poti sa raspunzi la intrebari.

Dem:

1) tabela se seteaza doar din 0 in 1. din cauza ca fiecare iteratie ori
schimba 1 intrare a matricei ori stabilizeaza matricea, dupa n^2 iteratii
am terminat.

2) lasa (a,b) /in VxV sa fie pozitii in graf pt care pisica are strategie.
o sa aratam ca dupa executia algoritmului, P[a][b] este 1. considera 
arborele de joc al acestei configurarii cu pisica care muta prima. acest
arbore are cel mult n^2 nivele (daca ar fi avut mai multe, din cauza
regulilor de egalitate, pisica nu are strategie de cashtig) acum considera
fiecare nod in acest arbore in care pisica este la mutare. pisica are
strategie de cashtig pt (a,b) deci are si pt orice nod in arbore in care
este la mutare. acum taie toti copiii care nu au de a face cu alegerea 
pisicii (ii tai pe toti in afara de cel pe care il alege pisica la pozitia
respectiva). acum uite-te la mutarea pisicii cea mai de jos (chiar deasupra
frunzelor) pisica are strategie de cashtig -> pisica trebuie sa aibe
strategie de cashtig pt nodul respectiv. intradevar, P[a'][b'] este 1
din cauza conditiilor (1). acum considera un nod a'' in interiorul grafului.
observa ca toate nodurile de sub a'' in care pisica este la mutare au fost 
setate P[x][y]=1, deci P[a''][b''] va fi setat la 1 (conditia 2).

3) cealalta parte a demonstratie este triviala, daca P[a][b] este setat la 1,
atunci pisica are strategie de cashti, practic exista o mutare a pisicii,
a. i. pt orice mutare a soarecelui, in n^2 mutari il va prinde. (numarul
maxim de mutari este chiar rankul nodului in arborele de joc)