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 de grad maxim și cealaltă extremitate de grad minim. 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_1.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_1.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_1.in

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

graf_partial_1.out

2
0 0 0 0 0 0 
0 0 1 1 0 0 
0 1 0 1 1 0 
0 1 1 0 1 0 
0 0 1 1 0 0 
0 0 0 0 0 0 

Explicație

Se elimină muchiile (1 3), (6 4).

#include <bits/stdc++.h>
using namespace std;
ifstream fin("graf_partial_1.in");
ofstream fout("graf_partial_1.out");
int a[105][105];
int main()
{
    int n , x , y , mini=1000000 , maxi=0 , cnt = 0;
    fin >> n;
    while(fin >> x >> y)
    {
        if (!a[x][y])
        {
            a[x][0]++;
            a[y][0]++;
        }
        a[x][y]=1;
        a[y][x]=1;
    }
    for (int i = 1; i <= n; i++)
    {
        mini = min(mini, a[i][0]);
        maxi = max(maxi, a[i][0]);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (a[i][0] == mini)
        {
            for (int j = 1; j <= n; j ++)
                if (a[j][0] == maxi && a[i][j] == 1)
                {
                    a[i][j] = 0;
                    a[j][i] = 0;
                    cnt++;
                }
        }
    }
    fout << cnt << endl;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= n ; j++)
            fout << a[i][j] << " ";
        fout << endl;
    }
    return 0;
}