Corjuc Eunice: /* Exemplul 2 */

2024-01-02T19:32:34Z

Exemplul 2

← Older revision		Revision as of 19:32, 2 January 2024
Line 21:		Line 21:

	0 1		0 1

			Explicație:

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

	== Exemplul 2 ==		== Exemplul 2 ==

Corjuc Eunice: Pagină nouă: = 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 numerel...

2023-12-16T14:29:07Z

Pagină nouă: = Cerința = Se dau două numere <code>n</code> și <code>m</code>. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> 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 <code>n m</code>. = Date de ieșire = Programul va afișa pe ecran numerel...

New page

= Cerința =
Se dau două numere <code>n</code> și <code>m</code>. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> 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 <code>n m</code>.

= Date de ieșire =
Programul va afișa pe ecran numerele <code>a</code> și <code>b</code>, reprezentând numărul minim, respectiv numărul maxim de noduri izolate într-un graf neorientat cu <code>n</code> noduri și <code>m</code> 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 =

* <code>1 ≤ n ≤ 100.000</code>
* 0<=m<=n*(n-1)/2

= Exemplul 1 =
Input:

4 2

Output:

0 1

== Exemplul 2 ==
Input:

99999999 2

Output:

Restrictiile nu sunt indeplinite.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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}")

</syntaxhighlight>

2636 - Noduri Izolate - Revision history

Corjuc Eunice: /* Exemplul 2 */