0549 - Epidemie

Cerința

Într-o țară locuiesc n persoane. Anumite perechi de persoane se cunosc între ele și se cunosc aceste perechi. Relația de cunoaștere între două persoane este reciprocă.

În țară izbucnește o epidemie (nu este mortală, doar foarte contagioasă). Dacă persoana A este bolnavă și cunoaște persoana B, se va îmbolnăvi și aceasta, după o perioadă de incubație a bolii de 1 zi. Inițial sunt bolnave k persoane cunoscute. Se cere să se determine după câte zile sunt bolnave toate cele n persoane.

Date de intrare

Fișierul de intrare epidemieIN.txt conține pe prima linie numerele n m, reprezentând numărul persoanelor și numărul perechilor de persoane care se cunosc reciproc. Urmează m linii cu câte două numere i j, cu semnificația: persoanele i și j se cunosc. Pe următoarea linie se află numărul k de persoane infectate inițial, iar pe ultima linie se află k numere distincte cuprinse între 1 și n, reprezentând aceste persoane.

Date de ieșire

Fișierul de ieșire epidemieOUT.txt va conține pe prima linie numărul Z, reprezentând numărul de zile după care toate cele n persoane sunt infectate.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ n*(n-1)/2
• 1 ≤ i , j ≤ n
• 1 ≤ k ≤ n
• ziua inițială va fi luată în considerare
• graful asociat acestei populații este conex

Exemplul 1

epidemieIN.txt

10 12
1 2
1 7
1 10
2 4
2 5
2 6
3 4
4 5
5 6
7 8
8 10
9 10
2
4 8

epidemieOUT.txt

3

Explicație

În prima zi se îmbolnăvesc persoanele: 4 8. În ziua a doua se infectează 2 3 5 7 10. În ziua a treia se infectează 1 6 9.

Exemplul 2

epidemieIN.txt

4 5
1 2
2 3
3 4
4 1
1 3
2
1 5

epidemieOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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

def citeste_input(file_path):

   with open(file_path, 'r') as file:
       n, m = map(int, file.readline().split())
       cunostinte = defaultdict(list)
       for _ in range(m):
           i, j = map(int, file.readline().split())
           cunostinte[i].append(j)
           cunostinte[j].append(i)
       k = int(file.readline())
       persoane_infectate = set(map(int, file.readline().split()))
   return n, m, cunostinte, k, persoane_infectate

def verifica_restrictii(n, m, cunostinte, k, persoane_infectate):

   if not (1 <= n <= 1000) or not (1 <= m <= n*(n-1)//2) or not (1 <= k <= n):
       return False
   for i, j in cunostinte.items():
       for vecin in j:
           if not (1 <= i <= n) or not (1 <= vecin <= n):
               return False
   if any(persoana <= 0 or persoana > n for persoana in persoane_infectate):
       return False
   return True

def rezolva(n, cunostinte, k, persoane_infectate):

   zile = 0
   infectate = set(persoane_infectate)
   queue = deque(persoane_infectate)
   while queue:
       zile += 1
       for _ in range(len(queue)):
           persoana = queue.popleft()
           for vecin in cunostinte[persoana]:
               if vecin not in infectate:
                   infectate.add(vecin)
                   queue.append(vecin)
   return zile

def scrie_output(file_path, zile):

   with open(file_path, 'w') as file:
       file.write(str(zile))

if __name__ == "__main__":

   input_file = "epidemieIN.txt"
   output_file = "epidemieOUT.txt"

   n, m, cunostinte, k, persoane_infectate = citeste_input(input_file)
   
   if verifica_restrictii(n, m, cunostinte, k, persoane_infectate):
       zile = rezolva(n, cunostinte, k, persoane_infectate)
       scrie_output(output_file, zile)
   else:
       with open(output_file, 'w') as file:
           file.write("Datele nu corespund restrictiilor impuse")

</syntaxhighlight>