Vizualizare sursă pentru „4304 - FF”

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