👤
a fost răspuns

Problema #2888 Spanning Tree PBINFO

Se consideră un graf neorientat conex cu n noduri și n muchii.

Cerința
Să se determine numărul arborilor parțiali ai grafului.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n perechi de numere naturale x y reprezentând cele n muchii.

Date de ieșire
Programul va afișa pe ecran numărul arborilor parțiali ai grafului.

Restricții și precizări
1 ≤ n ≤ 30.000
cele n muchii sunt distincte două câte două

Exemplu
Intrare

7
1 4
1 5
2 3
2 4
4 5
4 6
4 7
Ieșire

3

Răspuns :

BACIUNESSEN

Răspuns:

#include <fstream>

#define DMAX 210

using namespace std;

ifstream fin("partial.in");

ofstream fout("partial.out");

int n, a, b, elim, ic, sc, C[DMAX], newM[DMAX][DMAX];

bool M[DMAX][DMAX], viz[DMAX];

int main()

{

   int i, j, acum;

   fin >> n;

   while (fin >> a >> b)

       M[a][b] = M[b][a] = 1;

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

   {

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

       {

           if (M[i][j])

               elim++;

       }

   }

   elim /= 2;

   ic = 0;

   sc = -1;

   C[++sc] = 1;

   while (ic <= sc)

   {

       acum = C[ic++];

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

       {

           if (M[acum][i])

           {

               if (!viz[i])

               {

                   viz[i] = 1;

                   C[++sc] = i;

                   newM[acum][i] = newM[i][acum] = 1;

               }

               else

               {

                   if (elim && !newM[acum][i])

                   {

                       elim--;

                       newM[acum][i] = newM[i][acum] = -1;

                   }

                   else if (newM[acum][i] != -1 && newM[i][acum] != -1)

                       newM[acum][i] = newM[i][acum] = 1;

               }

           }

       }

   }

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

   {

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

       {

           if (newM[i][j] == -1)

               newM[i][j] = 0;

           fout << newM[i][j] << ' ';

       }

       fout << '\n';

   }

   fout.close();

   return 0;

}

SUCCESE !!! :)

Explicație:

Vă mulțumim că ați vizitat site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Dacă aveți întrebări sau nevoie de asistență suplimentară, nu ezitați să ne contactați. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


En Learnings: Alte intrebari