Rus Marius: /* Rezolvare */

2024-01-06T18:18:19Z

Rezolvare

← Older revision		Revision as of 18:18, 6 January 2024
Line 49:		Line 49:
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def citeste_graf(filename):		def citeste_graf(filename):
	with open(filename, 'r') as file:		try:
	~~try~~:		with open(filename, 'r') as file:
	n, m = map(int, file.readline().split())		n, m = map(int, file.readline().split())
	graf = {}		graf = {}
Line 57:		Line 57:
	i, j = map(int, file.readline().split())		i, j = map(int, file.readline().split())
	muchii.append((i, j))		muchii.append((i, j))
	~~if i not in~~ graf:		graf.setdefault(i, []).append(j)
	~~graf[~~i~~] =~~ []		graf.setdefault(j, []).append(i)
	~~if j not in graf:~~
	~~graf[j] = []~~
	~~graf[i]~~.append(j)
	graf[j].append(i)
	p, q = map(int, file.readline().split())		p, q = map(int, file.readline().split())
	except ValueError:		return n, m, muchii, graf, p, q
	return None, None, None, None, None, None		except ValueError:
			return None, None, None, None, None, None
	return n, m, ~~muchii~~, ~~graf~~, p, q		except FileNotFoundError:
			print(f"Fisierul {filename} nu a fost gasit.")
			return None, None, None, None, None, None
			except Exception as e:
			print(f"A aparut o eroare la citirea fisierului {filename}: {e}")
			return None, None, None, None, None, None

	def verifica_restrictii(n, m, muchii, p, q):		def verifica_restrictii(n, m, muchii, p, q):
Line 121:		Line 122:
	file.write("Nu există lanț între vârfurile date")		file.write("Nu există lanț între vârfurile date")

	# ~~Apelul funcției pentru datele din fișierul~~ de intrare ~~lantmaximIN.txt și scrierea rezultatului~~ în ~~lantmaximOUT.txt~~		def main():
	~~lanț_maxim~~("~~lantmaximIN.txt~~", "~~lantmaximOUT.txt~~")		try:
			# Get input and output filenames from the user
			input_filename = input("Introduceți numele fișierului de intrare: ")
			output_filename = input("Introduceți numele fișierului de ieșire: ")

			# Call the lanț_maxim function with the provided filenames
			lanț_maxim(input_filename, output_filename)

			print(f"Rezultatele au fost scrise în {output_filename}")
			except Exception as e:
			print(f"A apărut o eroare: {e}")

			if __name__ == "__main__":
			main()

	</syntaxhighlight>		</syntaxhighlight>

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri și două vârfuri `p q`. Să se determine cel mai lung lanț elementar cu extremitățile `p` și `q`. = Date de intrare = Fişierul de intrare `lantmaximIN.txt` conţine pe prima linie numerele `n` și `m`, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele...

2023-12-30T13:00:53Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>. = Date de intrare = Fişierul de intrare <code>lantmaximIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaximIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține două numere <code>p q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantmaximOUT.txt</code> va conține cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q ≤ n</code>
* pentru toate datele de test, va exista cel puțin un lanț cu extremitățile <code>p q</code>

= Exemplul 1: =
<code>lantmaximIN.txt</code>
5 7
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
2 1 3 4 5

= Exemplul 2: =
<code>lantmaximIN.txt</code>
100 100
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_graf(filename):
with open(filename, 'r') as file:
try:
n, m = map(int, file.readline().split())
graf = {}
muchii = []
for _ in range(m):
i, j = map(int, file.readline().split())
muchii.append((i, j))
if i not in graf:
graf[i] = []
if j not in graf:
graf[j] = []
graf[i].append(j)
graf[j].append(i)
p, q = map(int, file.readline().split())
except ValueError:
return None, None, None, None, None, None

return n, m, muchii, graf, p, q

def verifica_restrictii(n, m, muchii, p, q):
if not (1 <= n <= 20):
return False
for i, j in muchii:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
if not (1 <= p <= n) or not (1 <= q <= n):
return False
return True

def dfs(graf, start, end, path, visited, results):
visited[start] = True
path.append(start)

if start == end:
results.append(path.copy())

for neighbor in graf[start]:
if not visited[neighbor]:
dfs(graf, neighbor, end, path, visited, results)

path.pop()
visited[start] = False

def lanț_maxim(filename_in, filename_out):
n, m, muchii, graf, p, q = citeste_graf(filename_in)

if n is None:
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

if not verifica_restrictii(n, m, muchii, p, q):
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

visited = {v: False for v in graf}
results = []

dfs(graf, p, q, [], visited, results)

if results:
results.sort()
result = results[0]

with open(filename_out, 'w') as file:
file.write(' '.join(map(str, result)))
else:
with open(filename_out, 'w') as file:
file.write("Nu există lanț între vârfurile date")

# Apelul funcției pentru datele din fișierul de intrare lantmaximIN.txt și scrierea rezultatului în lantmaximOUT.txt
lanț_maxim("lantmaximIN.txt", "lantmaximOUT.txt")

</syntaxhighlight>

0479 - Lant Maxim - Revision history

Rus Marius: /* Rezolvare */