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

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")