Editing 4067 - CcMax

= Cerinţa =
Se dă un graf neorientat cu <code>n</code> 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 <code>ccmaxIN.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>ccmaxOUT.txt</code> 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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* în fișierul de intrare muchiile se pot repeta

= Exemplul 1 =
<code>ccmaxIN.txt</code>
 7
 1 5 
 3 5
 2 4
 6 4
<code>ccmaxOUT.txt</code>
 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 ==
<code>ccmaxIN.txt</code>
 101
<code>ccmaxOUT.txt</code>
 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>