0539 - DFS

Enunț

Se consideră un graf neorientat cu n vârfuri și m muchii și de asemenea un vârf X.

Cerinţa

Să se afișeze vârfurile vizitate în urma parcurgerii în adâncime (Depth First Search) a grafului, pornind din vârful X.

Date de intrare

Fişierul de intrare dfsIN.txt conţine pe prima linie trei numere naturale n, m, X, având următoarea semnificație: n este numărul de noduri, m este numărul de muchii din graf, iar X este vârful din care se începe parcurgerea. Următoarele m linii conțin câte două numere i j cu semnificația că există muchie între i și j .

Date de ieşire

Fişierul de ieşire dfsOUT.txt va conţine pe prima linie vârfurile vizitate în urma parcurgerii în adâncime a grafului, aceasta începând din vârful X.

Restricţii şi precizări

• 2 ≤ n ≤ 100
• 1 ≤ m ≤ n*(n-1)/2
• dacă în timpul parcurgerii, la un moment dat vârful curent al grafului este Y, vecinii nevizitați ai lui Y se vor analiza în ordine crescătoare.

Exemplul 1

dfsIN.txt

7 8 3
1 2
1 3
1 6
2 4
2 5
3 6
3 7
4 6

dfsOUT.txt

3 1 2 4 6 5 7 

Exemplul 2

dfsIN.txt

1 1 1

dfsOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, m):

   return 2 <= n <= 100 and 1 <= m <= n * (n - 1) / 2

def parcurgere_adancime(graf, start, vizitate):

   rezultat = []

   def dfs(node):
       nonlocal rezultat
       vizitate[node] = True
       rezultat.append(node)

       for neighbor in sorted(graf[node]):
           if not vizitate[neighbor]:
               dfs(neighbor)

   dfs(start)
   return rezultat

1. Citirea datelor de intrare

with open('dfsIN.txt', 'r') as file:

   n, m, X = map(int, file.readline().split())
   muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

1. Verificarea restricțiilor

if not verificare_restrictii(n, m):

   with open('dfsOUT.txt', 'w') as file_out:
       file_out.write("Datele nu corespund restrictiilor impuse")

else:

   # Inițializarea grafului reprezentat prin listă de adiacență
   graf = {i: [] for i in range(1, n + 1)}
   for muchie in muchii:
       graf[muchie[0]].append(muchie[1])
       graf[muchie[1]].append(muchie[0])

   # Inițializarea listei de vârfuri vizitate
   vizitate = {i: False for i in range(1, n + 1)}

   # Parcurgerea în adâncime a grafului
   rezultat_parcurgere = parcurgere_adancime(graf, X, vizitate)

   # Scrierea rezultatului în fișierul de ieșire
   with open('dfsOUT.txt', 'w') as file_out:
       if rezultat_parcurgere:
           file_out.write(' '.join(map(str, rezultat_parcurgere)))
       else:
           file_out.write("Datele nu corespund restrictiilor impuse")

</syntaxhighlight>