2636 - Noduri Izolate
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ă o 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ă o 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
- 0<=m<=n*(n-1)/2
Exemplul 1
Input:
4 2
Output:
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)
.
Exemplul 2
Input:
99999999 2
Output:
Restrictiile nu sunt indeplinite.
Rezolvare
def check_restrictions(n, m):
return 1 <= n <= 100000 and 0 <= m <= n * (n - 1) // 2
def calculate_isolated_nodes(n, m):
# Verifică restricțiile
if not check_restrictions(n, m):
print("Restrictiile nu sunt indeplinite.")
return None
# Numărul minim de noduri izolate
min_isolated_nodes = 0
# Numărul maxim de noduri izolate
max_isolated_nodes = max(0, min(n - m, 1))
return min_isolated_nodes, max_isolated_nodes
if __name__ == "__main__":
n = int(input("Introduceti numarul de noduri (n): "))
m = int(input("Introduceti numarul de muchii (m): "))
result = calculate_isolated_nodes(n, m)
if result is not None:
min_isolated, max_isolated = result
print(f"Numarul minim de noduri izolate: {min_isolated}")
print(f"Numarul maxim de noduri izolate: {max_isolated}")