Simina: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri, etichetate de la `1` la `n`. 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 `graf_partialIN.txt` conţine pe prima linie numărul `n`, reprezentând numărul de vârfuri ale grafului. Fie...

2023-12-12T22:36:18Z

Pagină nouă: = 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. Fie...

New page

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

0420 - Graf Partial - Revision history