Editing 0420 - Graf Partial (section)

= 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>