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 precizări

1 ≤ n ≤ 30.000
cele n muchii sunt distincte două câte două

Exemplul 1:

Intrare

Ieșire

Exemplul 2:

Intrare

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>