Rus Marius: /* Exemplul 1: */

2024-01-06T18:24:09Z

Exemplul 1:

← Older revision		Revision as of 18:24, 6 January 2024
Line 14:		Line 14:
	* Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.		* Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.
	* Numărul de muchii va fi mai mic decât <code>1.000.000</code>.		* Numărul de muchii va fi mai mic decât <code>1.000.000</code>.
			*
	= Exemplul 1: =		=Exemplul 1:=
	Intrare		Intrare
	4

	4

	1 2		1 2
			2 3
	2 3

	3 4		3 4

	4 1		4 1


	Ieșire		Ieșire
	2		2

Rus Marius: Pagină nouă: = Cerința = Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează. O față este o regiune înconjurată de muchii. = Date de intrare = Se vor citi repetat de la tastatură muchiile grafului. = Date de ieșire = Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu coresp...

2023-12-30T14:49:24Z

Pagină nouă: = Cerința = Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează. O față este o regiune înconjurată de muchii. = Date de intrare = Se vor citi repetat de la tastatură muchiile grafului. = Date de ieșire = Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu coresp...

New page

= Cerința =
Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează.

O față este o regiune înconjurată de muchii.

= Date de intrare =
Se vor citi repetat de la tastatură muchiile grafului.

= Date de ieșire =
Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.
* Numărul de muchii va fi mai mic decât <code>1.000.000</code>.

= Exemplul 1: =
Intrare
4

4

1 2

2 3

3 4

4 1

Ieșire
2

=== Explicație ===
Graful se poate desena sub forma unui pătrat. Are doar o față, la care se adaugă și regiunea exterioară.

== Exemplul 2: ==
Intrare
10000000
1000000000000000
Ieșire
Nu corespunde restricțiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restricții(numar_varfuri, numar_muchii):
return 0 < numar_varfuri < 1000000 and 0 < numar_muchii < 1000000

def numar_fețe(numar_varfuri, numar_muchii):
# Folosim formula lui Euler pentru grafuri planare: V - E + F = 2
# Deoarece graful este conex, V = E + 2, deci substituim în formulă.
# Obținem E + 2 - E + F = 2, și astfel F = 2.
return 2

def main():
try:
numar_varfuri = int(input("Introduceți numărul de vârfuri ale grafului: "))
numar_muchii = int(input("Introduceți numărul de muchii ale grafului: "))

if not verificare_restricții(numar_varfuri, numar_muchii):
print("Nu corespunde restricțiilor impuse.")
return

numar_muchii_introduse = 0
while numar_muchii_introduse < numar_muchii:
input_muchie = input(f"Introduceți o muchie sub forma x y (muchiile introduse: {numar_muchii_introduse}/{numar_muchii}): ")

if ' ' in input_muchie:
v1, v2 = map(int, input_muchie.split())

if 0 < v1 <= numar_varfuri and 0 < v2 <= numar_varfuri:
numar_muchii_introduse += 1
else:
print(f"Vârfurile muchiei trebuie să fie între 1 și {numar_varfuri} inclusiv.")
else:
print("Introduceți o pereche validă de vârfuri sub forma x y.")

rezultat = numar_fețe(numar_varfuri, numar_muchii)
print(f"Numărul de fețe al grafului este: {rezultat}")

except ValueError:
print("Introduceți numere valide pentru numărul de vârfuri și muchii.")

if __name__ == "__main__":
main()

</syntaxhighlight>

3147 - Fete Graf - Revision history

Rus Marius: /* Exemplul 1: */