Editing 0420 - Graf Partial

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri, etichetate de la <code>1</code> la <code>n</code>. Din acest graf se elimină toate muchiile cu proprietatea că ambele extremități au aceeași paritate. Să se determine câte muchii va avea graful parțial obținut.

= Date de intrare =
Fişierul de intrare <code>graf_partialIN.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>graf_partialOUT.txt</code> va conţine pe prima linie numărul <code>M</code> de muchii ale grafului parțial obținut.

= 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>graf_partialIN.txt</code>
 5
 1 4
 3 5
 2 3
 2 1
 4 2
 3 2
 1 3
<code>graf_partialOUT.txt</code>
 3

= Explicație =
Se elimină muchiile <code>(3 5)</code>, <code>(4 2)</code>, <code>(1 3)</code>. Graful parțial obținut va avea muchiile <code>(1 4)</code>, <code>(2 3)</code> și <code>(2 1)</code>.

== Exemplul 1 ==
<code>graf_partialIN.txt</code>
 1000
<code>graf_partialOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restricții(n, muchii):
    # Verifică restricția 1: 1 ≤ n ≤ 100
    if not (1 <= n <= 100):
        return False

    # Verifică restricția 2: 1 ≤ i, j ≤ n pentru fiecare muchie
    for muchie in muchii:
        i, j = muchie
        if not (1 <= i <= n) or not (1 <= j <= n):
            return False

    return True

def elimina_muchiile_paritare(n, muchii):
    graf_partial = set()

    for muchie in muchii:
        i, j = muchie
        if i % 2 != j % 2:
            graf_partial.add(tuple(sorted(muchie)))

    return graf_partial

def main():
    # Citeste datele de intrare
    with open("graf_partialIN.txt", "r") as f:
        n = int(f.readline().strip())
        muchii = [list(map(int, line.strip().split())) for line in f]

    # Verifică restricțiile
    if not verificare_restricții(n, muchii):
        # Scrie mesajul în fișierul de ieșire
        with open("graf_partialOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return

    # Elimina muchiile cu extremitati de aceeasi paritate
    graf_partial = elimina_muchiile_paritare(n, muchii)

    # Scrie doar numarul de muchii in fisierul de iesire
    with open("graf_partialOUT.txt", "w") as f:
        f.write(str(len(graf_partial)) + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>