Rezolvare completă PbInfo #2888 Spanning Tree

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).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Spanning Tree:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2888 Spanning Tree

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2888 Spanning Tree de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!