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ăspunsuri la întrebare
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: