GRAF COMPLET

Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet.

Date de intrare

Fişierul de intrare graf_complet.in conţine pe prima linie numărul de grafuri G. Pentru fiecare dintre cele G grafuri se dă n și apoi matricea de adiacență, formată din n linii și n coloane.

Date de ieşire

Fişierul de ieşire graf_complet.out va conţine G linii. Pe fiecare dintre ele se va afla mesajul DA sau NU, după cum graful corespunzător este sau nu complet.

Restricţii şi precizări

  • 1 ≤ G ≤ 5
  • 1 ≤ n ≤ 50

Exemplu

graf_complet.in

2
3
0 1 1
1 0 1
1 1 0
4
0 1 1 1
1 0 0 1
1 0 0 1
1 1 1 0

graf_complet.out

DA
NU

Explicație

S-au dat două grafuri. Primul are 3 vârfuri și este complet, al doilea are 4 vârfuri și nu este complet.

SOLUTIE

#include <bits/stdc++.h>

using namespace std;

ifstream f("graf_complet.in");
ofstream g("graf_complet.out");

int a[100][100];

int main()
{
    int n, m;

    f >> n;

    for(int k = 1; k <= n; k++)
    {
        f >> m;

        int ok = 1, x;

        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= m; j++)
            {
                f >> a[i][j];
            }

        for(int i = 1; i <= m && ok; i++)
            for(int j = 1; j <= m && ok; j++)
            {
                if(a[i][j] == 0 && i != j)
                    ok = 0;
                else
                if(a[i][j] != a[j][i])
                ok = 0;
            }

        if(ok == 1)
                g << "DA" << '\n';
            else
                g<< "NU" << '\n';

    }

    return 0;
}
%d bloggers like this: