# PBinfo #2888 – Spanning Tree – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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
Explicație
Graful din exemplu corespunde imaginii de mai jos.



Primul arbore parțial este format din muchiile: (1, 4), (2, 3), (2, 4), (4, 5), (4, 6), (4, 7).
Al doilea arbore parțial este format din muchiile: (1, 4), (1, 5), (2, 3), (2, 4), (4, 6), (4, 7).
Al treilea arbore parțial este format din muchiile: (1, 5), (2, 3), (2, 4), (4, 5), (4, 6), (4, 7).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define nmax 30003
using namespace std;
vector<int> L[nmax];
int n, d[nmax];
int X, Y, viz[nmax];
void Citire()
{
    int i, j;
    cin >> n;
    while (cin >> i >> j)
    {
        L[i].push_back(j);
        L[j].push_back(i);
    }
}
void DFS(int k, int tata)
{
    viz[k] = 1;
    for (auto i : L[k])
        if (viz[i] == 0) DFS(i, k);
        else if (i != tata)
        {
            X = i; Y = k;
        }
}
void Sterge(int x, int y)
{
    unsigned int len = L[x].size();
    for (unsigned int i = 0; i < len; i++)
        if (L[x][i] == y)
        {
            L[x][i] = L[x][len - 1];
            L[x].pop_back();
            return;
        }
}
void BFS()
{
    int k;
    /// sterge muchia (X, Y)
    Sterge(X, Y);
    Sterge(Y, X);
    queue <int> q;
    q.push(X);
    d[X] = 1;
    while (!q.empty())
    {
        k = q.front();
        q.pop();
        for (auto i : L[k])
            if (d[i] == 0)
            {
                d[i] = 1 + d[k];
                q.push(i);
            }
    }
    cout << d[Y] << "\n";
}
int main()
{
    Citire();
    DFS(1, 0);
    BFS();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2888)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2888/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2888/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)