4067 - CcMax

Cerinţa

Se dă un graf neorientat cu n vârfuri. Determinați numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest număr maxim de vârfuri.

Date de intrare

Fişierul de intrare ccmaxIN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire ccmaxOUT.txt va conţine pe prima linie numărul maxim de vârfuri dintr-o componentă conexă și numărul de componente conexe care au acest numar maxim de vârfuri, separate prin exact un spațiu.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• în fișierul de intrare muchiile se pot repeta

Exemplul 1

ccmaxIN.txt

7
1 5 
3 5
2 4
6 4

ccmaxOUT.txt

3 2

Explicație:

Graful conține două componente cu număr maxim de vârfuri, fiecare având câte 3 vârfuri. Acestea sunt {1,3,5} și {2,4,6}, iar vârful 7 este izolat.

Exemplul 2

ccmaxIN.txt

101

ccmaxOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def parcurgere_dfs(nod, vizitat, graf):

   vizitat[nod] = True
   dimensiune = 1
   for vecin in graf[nod]:
       if not vizitat[vecin]:
           dimensiune += parcurgere_dfs(vecin, vizitat, graf)
   return dimensiune

def verificare_restrictii(n, muchii):

   if not (1 <= n <= 100):
       return False
   for i, j in muchii:
       if not (1 <= i <= n) or not (1 <= j <= n):
           return False
   return True

def main():

   with open("ccmaxIN.txt", "r") as infile:
       n = int(infile.readline().strip())
       muchii = [tuple(map(int, linie.split())) for linie in infile]

       if not verificare_restrictii(n, muchii):
           with open("ccmaxOUT.txt", "w") as outfile:
               outfile.write("Datele nu corespund restrictiilor impuse\n")
           return

       graf = {i: [] for i in range(1, n + 1)}
       for i, j in muchii:
           graf[i].append(j)
           graf[j].append(i)

   dim_maxima = 0
   numar_dim_maxima = 0
   vizitat = [False] * (n + 1)

   for nod in range(1, n + 1):
       if not vizitat[nod]:
           dimensiune_componenta = parcurgere_dfs(nod, vizitat, graf)
           if dimensiune_componenta > dim_maxima:
               dim_maxima = dimensiune_componenta
               numar_dim_maxima = 1
           elif dimensiune_componenta == dim_maxima:
               numar_dim_maxima += 1

   with open("ccmaxOUT.txt", "w") as outfile:
       if dim_maxima == 0:
           outfile.write("Datele nu corespund restrictiilor impuse\n")
       else:
           outfile.write(f"{dim_maxima} {numar_dim_maxima}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>