Vizualizare sursă pentru „2888 - Spanning Tree”

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

= 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>