Components connexos P94041


Statement
 

pdf   zip

thehtml

En un graf no dirigit amb n nodes, i inicialment sense cap aresta, s’hi han d’inserir m arestes donades, en l’ordre en què es donen, i dient quants components connexos té el graf després de cada inserció.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits de les arestes. Cada aresta es descriu amb els seus dos vèrtexs. Suposeu 2 ≤ n ≤ 105, 1 ≤ m ≤ 2n, que els vèrtexs es numeren entre 0 i n−1, i que no hi ha arestes repetides, ni arestes que connectin un vèrtex amb ell mateix.

Sortida

Per a cada cas, escriviu una línia amb m nombres separats per espais: el k-èssim ha de ser el nombre de components connexos del graf si només considerem les k primeres arestes de l’entrada.

Public test cases
  • Input

    4 5
    0 1
    0 2
    1 2
    3 2
    3 1
    
    100000 4
    17 751
    17 1024
    0 99999
    1024 751
    

    Output

    3 2 2 1 1
    99999 99998 99997 99997
    
  • Information
    Author
    Pol Mauri
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++