1603 - Componente Conexe 3

Cerinţa

Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe. Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

Date de intrare

Fişierul de intrare componenteconexe3IN.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 componenteconexe3OUT.txt va conţine pe prima linie reprezentantul componentei conexe cu număr maxim de noduri și numărul maxim de noduri, 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
• dacă sunt mai multe componente conexe cu număr maxim de vârfuri se va determina aceea cu reprezentantul minim

Exemplul 1

componenteconexe3IN.txt

5
1 5 
3 5
2 4

componenteconexe3OUT.txt

1 3

Exemplul 2

componenteconexe3IN.txt

101

componenteconexe3OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, muchii):

   if not (1 <= n <= 100):
       return "Datele nu corespund restrictiilor impuse"

   for i, j in muchii:
       if not (1 <= i <= n and 1 <= j <= n):
           return "Datele nu corespund restrictiilor impuse"

   return None

def dfs(nod, vizitat, graf, componenta_curenta):

   vizitat[nod] = True
   componenta_curenta.append(nod)
   
   for vecin in graf[nod]:
       if not vizitat[vecin]:
           dfs(vecin, vizitat, graf, componenta_curenta)

def main():

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

   restrictii_mesaj = verificare_restrictii(n, muchii)

   if restrictii_mesaj:
       with open("componenteconexe3OUT.txt", "w") as fisier_iesire:
           fisier_iesire.write(restrictii_mesaj)
       return

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

   for muchie in muchii:
       graf[muchie[0]].append(muchie[1])
       graf[muchie[1]].append(muchie[0])

   vizitat = {i: False for i in range(1, n+1)}
   componente = []

   for nod in range(1, n+1):
       if not vizitat[nod]:
           componenta_curenta = []
           dfs(nod, vizitat, graf, componenta_curenta)
           componente.append(componenta_curenta)

   max_noduri = 0
   reprezentant = float('inf')

   for componenta in componente:
       if len(componenta) > max_noduri or (len(componenta) == max_noduri and min(componenta) < reprezentant):
           max_noduri = len(componenta)
           reprezentant = min(componenta)

   with open("componenteconexe3OUT.txt", "w") as fisier_iesire:
       if restrictii_mesaj:
           fisier_iesire.write(restrictii_mesaj)
       else:
           fisier_iesire.write(f"{reprezentant} {max_noduri}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>