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).

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("graf_partial_2.in");
ofstream fout ("graf_partial_2.out");
int a[101][101], n, x, y, mx, nr, m, mn = 1000000000;
int main()
{
    fin >> n;
    while(fin >> x >> y)
    {
        if (a[x][y] == 0)
        {
            a[x][0]++;
            a[y][0]++;
        }
        a[x][y] = 1;
        a[y][x] = 1;
        mx = max(mx, max(a[x][0], a[y][0]));
    }
    m = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if ((a[i][0] == mx || a[j][0] == mx)&&(a[i][j] == 1))
            {
                m++;
                a[i][j] = 0;
                a[j][i] = 0;
            }
        }
    }
    fout << m << endl;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)fout << a[i][j] << ' ';
        fout << endl;
    }
    return 0;
}