fbpx

Problema #2636 – Noduri – Rezolvari PBInfo

de Mihai-Alexandru

Cerința

Se dau două numere n și m. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există un muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Date de intrare

Programul citește de la tastatură numerele n m.

Date de ieșire

Programul va afișa pe ecran numerele a și b, reprezentând numărul minim, respectiv numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există un muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Restricții și precizări

  • 1 ≤ n ≤ 100.000
  • 0mn(n1)20mn(n1)2

Exemplu

Intrare

4 2

Ieșire

0 1

Explicație

Se poate construi un graf fără noduri izolate, cu muchiile (1,2) și (3,4). Pentru a obține un nod izolat, putem construi un graf cu muchiile (1,2) și (1,3).

#include <bits/stdc++.h>

using namespace std;

long long n , m , k;

int main()
{
    cin >> n >> m;
    
    if(m * 2 >= n) cout << 0 << " ";
    else cout << n - 2 * m << " ";

    while(k  * (k - 1) / 2 < m) k++;
    
    cout << n - k;

}
Comentarii

S-ar putea sa iti placa