Rezolvare PBinfo #422

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

Date de intrare

Fişierul de intrare graf_partial_2.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire graf_partial_2.out va conţine pe prime linie numărul de muchii eliminate, iar pe următoarele linii matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplu:

graf_partial_2.in

6
1 2
6 2
2 3
4 3
5 3
4 5
3 6
6 4

graf_partial_2.out

4
0 1 0 0 0 0 
1 0 0 0 0 1 
0 0 0 0 0 0 
0 0 0 0 1 1 
0 0 0 1 0 0 
0 1 0 1 0 0 

Explicație

Se elimină muchiile (2 3), (4 3), (5 3), (3 6).