Question

Problema #4072 de pe pbinfo Graf Partial 5
Cerinţa
Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n și un număr natural k. Din acest graf se elimină toate muchiile care au ambele extremități în vârfuri de grad mai mare sau egal cu k. Să se afișeze matricea de adiacență a grafului parțial obținut.

Date de intrare
Fişierul de intrare graf_partial_5.in conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului și numărul k. 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_5.out va conţine 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 < k < n ≤ 100
1 ≤ i , j ≤ n
muchiile se pot repeta în fișierul de intrare



Exemplu
graf_partial_5.in

6 3
1 4
2 5
2 4
2 1
4 5
3 2
4 3
2 6
3 6
graf_partial_5.out

0 1 0 1 0 0
1 0 0 0 1 1
0 0 0 0 0 1
1 0 0 0 1 0
0 1 0 1 0 0
0 1 1 0 0 0
Explicație
Se elimină muchiile (2 3), (4 3), (2 4) deoarece vârfurile 2, 3 și 4 au gradul mai mare sau egal cu 3.

Answer 1

Răspuns:

#include <fstream>

using namespace std;

ifstream f("graf_partial_5.in");

ofstream g("graf_partial_5.out");

int n, k, a[105][105], x, y;

void citire() {

   f >> n >> k;

   while(f >> x >> y)

       a[x][y] = a[y][x] = 1;

}

int grad_vf(int vf) {

   int grad = 0;

   for(int i = 1; i <= n; i++)

       if(a[vf][i])

           grad++;

   return grad;

}

int main() {

   citire();

   for(int i = 1; i <= n; i++)

       for(int j = 1; j <= n; j++)

           if(a[i][j])

               if(grad_vf(i) >= k && grad_vf(j) >= k)

                   a[i][j] = a[j][i] = 2;

               

   for(int i = 1; i <= n; i++, g << endl)

       for(int j = 1; j <= n; j++)

           if(a[i][j] == 2)

               g << 0 << " ";

           else g << a[i][j] << " ";

}

Explicație:

Punem 2 pe pozitiile pe care le modificam, dar de care mai avem inca nevoie pentru validare, iar la sfarsit le ignoram