2888 - Spanning Tree

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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 30.000
• cele n 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>