Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf.

Cerința

Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.

Date de intrare

Programul citește de la tastatură numerele n și m, iar pe următoarele m linii se află câte două valori x și y separate prin spațiu, reprezentând o muchie din graf. Muchiile vi se dau în ordinea în care ele se elimină din graf.

Date de ieșire

Programul va afișa pe ecran exact m linii, pe fiecare linie i aflându-se un singur număr natural reprezentând numărul componentelor conexe din graf după eliminarea celei de-a i-a muchii.

Restricții și precizări

1 ≤ n ≤ 100 000
1 ≤ m ≤ 500 000
Între două vârfuri va exista cel mult o muchie

Exemplu

Intrare

Ieșire

Explicație

Sunt 5 vârfuri și 6 muchii. Urmează cele 6 muchii în ordinea eliminării lor. După eliminarea muchiei 1 2 graful este tot conex, deci rezultatul este 1. După eliminarea muchiei 3 4 se obțin două componente conexe, una formată din vârfurile 2, 3, iar cealaltă componentă formată din vârfurile 1, 4, 5. Restul eliminărilor nu mai trebuie explicate că ați înțeles deja.

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 ComponenteConexe4:

#include <bits/stdc++.h>
#define nmax 100005
#define mmax 500005
using namespace std;

int t[nmax], n, m;
pair<int, int> M[mmax];
int answer[mmax];

/// returneaza nodul radacina din componenta conexa
/// din care face parte nodul x
inline int Find(int x)
{
    int rad, y;
    rad = x;
    while (t[rad] != 0) rad = t[rad];

    while (x != rad)
    {
        y = t[x];
        t[x] = rad;
        x = y;
    }
    return rad;
}

/// unifica componentele conexe care au ca radacini
/// nodurile x si y
inline void Union(int x, int y)
{
    t[y] = x;
}

int main()
{
    int i, x, y, nrCompCon;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> x >> y;
        M[i] = make_pair(x, y);
    }

    nrCompCon = n;
    for (i = m; i >= 1; i--)
    {
        answer[i] = nrCompCon;
        x = Find(M[i].first);
        y = Find(M[i].second);
        if (x != y)
        {
            Union(x, y);
            nrCompCon--;
        }
    }

    /// afisare
    for (i = 1; i <= m; i++)
        cout << answer[i] << "\n";
    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 #2282 ComponenteConexe4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2282 ComponenteConexe4 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!

Rezolvare completă PbInfo #2282 ComponenteConexe4