Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim. = Date de intrare = Fişierul de intrare `gradmaxIN.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 `...`


2023-12-12T21:40:14Z
Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim.  = Date de intrare = Fişierul de intrare <code>gradmaxIN.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>...
New page
= Cerinţa =

Se dă lista muchiilor unui graf neorientat. Să se afișeze vârfurile de grad maxim.



= Date de intrare =

Fişierul de intrare <code>gradmaxIN.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>gradmaxOUT.txt</code> va conţine pe prima linie numărul <code>m</code> de vârfuri de grad maxim, urmat de cele <code>m</code> vârfuri de grad maxim ,în ordine crescătoare, separate prin exact un spațiu.



= Restricţii şi precizări =



* <code>1 ≤ n ≤ 100</code>

* <code>1 ≤ i , j ≤ n</code>

* muchiile se pot repeta în fișierul de intrare



= Exemplul 1 =

<code>gradmaxIN.txt</code>

 5

 1 4

 2 5

 2 3

 2 1

 4 5

 3 2

 4 3

<code>gradmaxOUT.txt</code>

 2 2 4



= Exemplul 2 =

<code>gradmaxIN.txt</code>

 101

 1 4

 2 5

 2 3

 2 1

 4 5

 3 2

 4 3

<code>gradmaxOUT.txt</code>

 Datele nu corespund restrictiilor impuse



== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

def citeste_graf(file_path):

    with open(file_path, 'r') as file:

        n = int(file.readline().strip())



        # Verifica restricțiile pentru numărul de vârfuri

        if not (1 <= n <= 100):

            return None, None, "Datele nu corespund restrictiilor impuse"



        muchii = [tuple(map(int, line.strip().split())) for line in file]



        # Verifica restricțiile pentru vârfurile muchiilor

        for i, j in muchii:

            if not (1 <= i <= n) or not (1 <= j <= n):

                return None, None, "Datele nu corespund restrictiilor impuse"



    return n, muchii, None



def calculeaza_grad(n, muchii):

    grad = [0] * (n + 1)

    for i, j in muchii:

        grad[i] += 1

        grad[j] += 1

    return grad



def vafuri_grad_maxim(grad):

    max_grad = max(grad)

    vafuri_maxime = [i for i, val in enumerate(grad) if val == max_grad]

    return vafuri_maxime



def scrie_output(file_path, vafuri_maxime, eroare=None):

    with open(file_path, 'w') as file:

        if eroare:

            file.write(eroare)

        else:

            file.write(f"{len(vafuri_maxime)}\n")

            file.write(" ".join(map(str, vafuri_maxime)))



if __name__ == "__main__":

    file_input = "gradmaxIN.txt"

    file_output = "gradmaxOUT.txt"



    n, muchii, eroare = citeste_graf(file_input)



    scrie_output(file_output, [], eroare) if eroare else None



    if not eroare:

        grad = calculeaza_grad(n, muchii)

        vafuri_maxime = vafuri_grad_maxim(grad)

        scrie_output(file_output, vafuri_maxime)



</syntaxhighlight>

0417 - Grad Max - Revision history