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 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, semnificând existența în graful dat a unei muchii între nodurile x și y.

Date de ieșire

Fișierul de ieșire ffOUT.txt 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

• 1 ≤ n ≤ 100.000
• 1 ≤ m ≤ 200.000
• Se garantează existența unui astfel de subgraf.

Exemplul 1:

ffIN.txt

4 4
1 2
4 1
2 3
1 3

ffOUT.txt

3

Exemplul 2:

ffIN.txt

123921321 4
1 2
4 1
2 3
1 3

ffOUT.txt

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>