Simina: Pagină nouă: == 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...

2023-12-12T23:49:24Z

Pagină nouă: == 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...

New page

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

0539 - DFS - Revision history