Rezolvare PBinfo #1341

Decorative Icon Problema: Protest / 1341

Decorative IconAutor: Andrei

Cerința

În țara lui Zoli trăiesc n persoane, numerotate de la 1 la n, iar Zoli are numărul de ordine 1. Zoli s-a săturat de sistemul politic, așa că s-a decis să iasă în stradă. Deoarece Zoli este o persoană sociabilă, are prieteni din diverse cercuri pe care s-a gândit să îi cheme cu el. Zoli își va anunța prietenii, care la rândul lor își vor anunța prietenii și așa mai departe.

Știm însă că unele persoane sunt scandalagii, iar Zoli este un om pașnic și preferă să nu trimită invitația acestora.

Zoli vă cere să îi spuneți numărul de persoane cu care se va întâlni la protest.

Date de intrare

Fișierul de intrare protest.in conține pe prima linie numărul n, reprezentând numărul de prieteni și numărul k, reprezentând numărul de prieteni scandalagii.

A doua linie conține k numere, reprezentând numerele de ordine ale prietenilor scandalagii.

Următoarele n-1 linii vor conține câte două perechi de numere x y cu semnificația că persoana cu numărul de ordine x este prietenă cu persoana ce are numărul de ordine y.

Date de ieșire

Fișierul de ieșire protest.out va conține doar numărul nr, reprezentând numărul de prieteni care i se vor alătura lui Zoli.

Restricții și precizări
  • 1 ≤ n ≤ 50000
  • 1 ≤ k ≤ 1000
  • Numerele de ordine ale scandalagiilor vor fi mai mici decât n
  • Fiecare persoană poate anunța doar prietenii cu care are o legătură directă, rămânând pe seama celor din urmă să transmită invitația mai departe, dacă e posibil.
  • Relația de prietenie nu este reciprocă.
Exemplu:

protest.in

8 3
4 8 3
1 2
8 5
4 3
1 6
7 5
2 4
4 8

protest.out

2

Explicație

Zoli va anunța prietenii cu numerele de ordine 2 și 6.

Decorative Icon Explică rezolvarea folosind Inteligența Artificială

Folosește modelul nostru de AI special antrenament pentru a rezolva problemele de pe PBinfo! În baza creditelor AI primești explicații pentru probleme, pe care le alegi și le rulezi exact atunci când dorești, la un singur click distanță! Află mai multe informații:

👉 Achiziționează credite AI
Andrei Frîntu
Andrei Frîntu

Fondatorul platformei - mentor Academia

LinkedIn Instagram GitHub
© Copyright 2026 - CodulLuiAndrei.ro - Toate drepturile sunt rezervate