Editing 0539 - DFS

== Enunț ==
Se consideră un graf neorientat cu <code>n</code> vârfuri și <code>m</code> muchii și de asemenea un vârf <code>X</code>.

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

= Date de intrare =
Fişierul de intrare <code>dfsIN.txt</code> conţine pe prima linie trei numere naturale <code>n</code>, <code>m</code>, <code>X</code>, având următoarea semnificație: <code>n</code> este numărul de noduri, <code>m</code> este numărul de muchii din graf, iar <code>X</code> este vârful din care se începe parcurgerea. Următoarele <code>m</code> linii conțin câte două 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>dfsOUT.txt</code> va conţine pe prima linie vârfurile vizitate în urma parcurgerii în adâncime a grafului, aceasta începând din vârful <code>X</code>.

= Restricţii şi precizări =

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

= Exemplul 1 =
<code>dfsIN.txt</code>
 7 8 3
 1 2
 1 3
 1 6
 2 4
 2 5
 3 6
 3 7
 4 6
<code>dfsOUT.txt</code>
 3 1 2 4 6 5 7 

= Exemplul 2 =
<code>dfsIN.txt</code>
 1 1 1
<code>dfsOUT.txt</code>
 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

# 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)]

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