4304 - FF - Revision history

Rus Marius: Pagină nouă: = Cerința = Se dă un graf neorientat. Să se determine un subgraf al său, cu număr cât mai mare de noduri și în care fiecare nod are gradul cel puțin `2`. = Date de intrare = Fișierul de intrare `ffIN.txt` conține pe prima linie numerele `n` și `m` reprezentând numărul de noduri și numărul de muchii pentru graful dat. Fiecare din următoarele `m` linii conține două numere, `x` și y 2024-01-06T19:40:44Z Pagină nouă: = Cerința = Se dă un graf neorientat. Să se determine un subgraf al său, cu număr cât mai mare de noduri și în care fiecare nod are gradul cel puțin <code>2</code>. = Date de intrare = Fișierul de intrare <code>ffIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code> reprezentând numărul de noduri și numărul de muchii pentru graful dat. Fiecare din următoarele <code>m</code> linii conține două numere, <code>x</code> și <code>y</cod... New page = Cerința = Se dă un graf neorientat. Să se determine un subgraf al său, cu număr cât mai mare de noduri și în care fiecare nod are gradul cel puțin <code>2</code>. = Date de intrare = Fișierul de intrare <code>ffIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code> reprezentând numărul de noduri și numărul de muchii pentru graful dat. Fiecare din următoarele <code>m</code> linii conține două numere, <code>x</code> și <code>y</code>, semnificând existența în graful dat a unei muchii între nodurile <code>x</code> și <code>y</code>. = Date de ieșire = Fișierul de ieșire <code>ffOUT.txt</code> va conține valoarea ce reprezintă numărul maxim de noduri pe care le poate avea subgraful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". = Restricții și precizări = * <code>1 ≤ n ≤ 100.000</code> * <code>1 ≤ m ≤ 200.000</code> * Se garantează existența unui astfel de subgraf. = Exemplul 1: = <code>ffIN.txt</code> 4 4 1 2 4 1 2 3 1 3 <code>ffOUT.txt</code> 3 = Exemplul 2: = <code>ffIN.txt</code> 123921321 4 1 2 4 1 2 3 1 3 <code>ffOUT.txt</code> Datele nu corespund restrictiilor impuse == Rezolvare == <syntaxhighlight lang="python3" line="1"> from collections import deque Inf = 0x3f3f3f3f def check_restrictions(n, m): if not (1 <= n <= 100000 and 1 <= m <= 200000): with open("ffOUT.txt", "w") as outfile: outfile.write("Datele nu corespund restrictiilor impuse") return True return False def main(): with open("ffIN.txt", "r") as infile, open("ffOUT.txt", "w") as outfile: n, m = map(int, infile.readline().split()) if check_restrictions(n, m): return G = [[] for _ in range(n + 1)] g = [0] * (n + 1) f = [0] * (n + 1) scad = 0 for _ in range(m): x, y = map(int, infile.readline().split()) G[x].append(y) G[y].append(x) g[x] += 1 g[y] += 1 q = deque() for i in range(1, n + 1): if g[i] == 1: q.append(i) g[i] = 0 f[i] = 1 elif g[i] == 0: scad += 1 while q: x = q.popleft() scad += 1 for i in G[x]: g[i] -= 1 if g[i] < 2 and f[i] == 0: q.append(i) f[i] = 1 outfile.write(str(n - scad)) if name == "main": main() </syntaxhighlight>