Editing 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 <code>componenteconexe3IN.txt</code> conţine pe prima linie numărul <code>n</code>, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

= Date de ieşire =
Fişierul de ieşire <code>componenteconexe3OUT.txt</code> 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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* î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 =
<code>componenteconexe3IN.txt</code>
 5
 1 5 
 3 5
 2 4
<code>componenteconexe3OUT.txt</code>
 1 3

= Exemplul 2 =
<code>componenteconexe3IN.txt</code>
 101
<code>componenteconexe3OUT.txt</code>
 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>