Rus Marius: /* Date de ieșire */

2024-01-06T19:55:04Z

Date de ieșire

← Older revision		Revision as of 19:55, 6 January 2024
Line 9:		Line 9:

	= Date de ieșire =		= Date de ieșire =
	Programul va afișa pe ecran numărul arborilor parțiali ai grafului.		Programul va afișa pe ecran numărul arborilor parțiali ai grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Rus Marius: Pagină nouă: == Enunț == Se consideră un graf neorientat conex cu `n` noduri și `n` muchii. = Cerința = Să se determine numărul arborilor parțiali ai grafului. = Date de intrare = Programul citește de la tastatură numărul `n`, iar apoi `n` perechi de numere naturale `x y` reprezentând cele `n` muchii. = Date de ieșire = Programul va afișa pe ecran numărul arborilor parțiali ai grafului. = Restricții și...

2024-01-06T19:54:54Z

Pagină nouă: == Enunț == Se consideră un graf neorientat conex cu <code>n</code> noduri și <code>n</code> muchii. = Cerința = Să se determine numărul arborilor parțiali ai grafului. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> reprezentând cele <code>n</code> muchii. = Date de ieșire = Programul va afișa pe ecran numărul arborilor parțiali ai grafului. = Restricții și...

New page

== Enunț ==
Se consideră un graf neorientat conex cu <code>n</code> noduri și <code>n</code> muchii.

= Cerința =
Să se determine numărul arborilor parțiali ai grafului.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> reprezentând cele <code>n</code> muchii.

= Date de ieșire =
Programul va afișa pe ecran numărul arborilor parțiali ai grafului.

= Restricții și precizări =

* <code>1 ≤ n ≤ 30.000</code>
* cele <code>n</code> muchii sunt distincte două câte două

= Exemplul 1: =
Intrare
7
1 4
1 5
2 3
2 4
4 5
4 6
4 7
Ieșire
3

= Exemplul 2: =
Intrare
30001
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_restriction_n(value):
if not (1 <= value <= 30000):
print("Datele nu corespund restrictiilor impuse")
exit()

def main():
n = int(input())
check_restriction_n(n)

v = [[] for _ in range(30001)]
t = [0] * 30001
cnt = 0
q = deque()

for _ in range(n):
x, y = map(int, input().split())
v[x].append(y)
v[y].append(x)
t[x] += 1
t[y] += 1

for i in range(1, n + 1):
if t[i] == 1:
q.append(i)

while q:
x = q.popleft()
for y in v[x]:
if t[y]:
t[y] -= 1
if t[y] == 1:
q.append(y)
t[x] = 0

for i in range(1, n + 1):
if t[i] == 2:
cnt += 1

print(cnt)

if __name__ == "__main__":
main()

</syntaxhighlight>

2888 - Spanning Tree - Revision history

Rus Marius: /* Date de ieșire */