005 Graf2

[•wefgef]

Aici puteţi discuta despre problema Graf2.

[•hunter_ionutzzz]

cum pot să determin daca într-o componentă tare conexă de k noduri am nevoie de k muchii sau k+1 muchii ca să pot să obțin ciclu?

[•klamathix]

In ce caz ai putea sa ai nevoie de k + 1 muchii?

[•hunter_ionutzzz]

păi în cazul
1 2
1 3
2 4
3 4
4 1

[•klamathix]

Nu ai nevoie de 5 muchii. Ai nevoie de 4.
O poti reconstrui ca : 1 -> 2 , 2 -> 3 , 3 -> 4 , 4 -> 1.
Ca si in graful dat de tine, oricare 2 noduri sunt accesibile unul din celalalt.

[•hunter_ionutzzz]

arc 2 - 3 nu am în componentă și singura variantă este să folosesc toate muchiile ...

[•klamathix]

Nu trebuie sa ai. Il pui tu. Cerinta nu e sa tai cat mai multe muchii din graful pe care-l primesti si sa mentii drumurile. Te intreaba cate muchii are minim un graf care are aceleasi drumuri, dar nu exista nicio restrictie asupra muchiilor pe care ai voie sa le folosesti. Nu trebuie sa existe deja in graful initial sau ceva de genul asta.

[•hunter_ionutzzz]

de cand lucru la ea am si uitat ce imi cerea problema .... mersi mult , n-am fost atent   

[•ctlin04]

Dupa ce determinam componentele tare conexe, le comprimam in noduri si facem un alt graf, nu ar fi corect doar sa determinam componentele conexe din noul graf si pentru o componenta conexa care contine k noduri sa adaugam k-1 muchii la rezultat, in loc sa facem cum e scris in solutia oficiala? Daca nu e corect va rog dati-mi un contraexemplu. 

[•PlayLikeNeverB4]

Cod:

4 4
1 2
1 3
2 4
3 4

Iti da bine pe asta?

[•Cosmin1490]

Incerc de ceva timp sa ma prind unde am gresit la implementare si nu imi dau seama

Cat tre sa dea pe :

Cod:

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

si pe :

Cod:

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

Ar trebui sa dea 10 si 8  nu?