Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri și un vârf `q`. Să se determine cel mai lung lanț elementar cu extremitatea finală în `q`. = Date de intrare = Fişierul de intrare `lantmaxim1IN.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 `m` li...

2023-12-30T12:50:44Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>q</code>. Să se determine cel mai lung lanț elementar cu extremitatea finală în <code>q</code>. = Date de intrare = Fişierul de intrare <code>lantmaxim1IN.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> li...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>q</code>. Să se determine cel mai lung lanț elementar cu extremitatea finală în <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaxim1IN.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 numărul <code>q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantmaxim1OUT.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>
* <code>1 ≤ q ≤ n</code>

= Exemplul 1: =
<code>lantmaxim1IN.txt</code>
5 6
1 4
1 3
3 5
4 5
1 2
3 4
5
<code>lantmaxim1OUT.txt</code>
2 1 3 4 5

= Exemplul 2: =
<code>lantmaxim1IN.txt</code>
21 21
1 4
1 3
3 5
4 5
1 2
3 4
5
<code>lantmaxim1OUT.txt</code>
Nu corespunde restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, muchii, q):
if not (1 <= n <= 20):
return False
for u, v in muchii:
if not (1 <= u <= n) or not (1 <= v <= n):
return False
if not (1 <= q <= n):
return False
return True

def gestionare_restrictii(file_path_out):
with open(file_path_out, 'w') as file_out:
file_out.write("Nu corespunde restrictiilor impuse")
exit()

def citeste_graf(file_path):
with open(file_path, 'r') as file:
n, m = map(int, file.readline().split())
muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

try:
q = int(file.readline())
except ValueError:
gestionare_restrictii("lantmaxim1OUT.txt")

if not verifica_restrictii(n, muchii, q):
gestionare_restrictii("lantmaxim1OUT.txt")

return n, muchii, q

def dfs_lant_maxim(q, graf, vizitat, path, lant_maxim):
vizitat[q] = True
path.append(q)

for vecin in graf[q]:
if not vizitat[vecin]:
dfs_lant_maxim(vecin, graf, vizitat, path, lant_maxim)

if len(path) >= len(lant_maxim):
lant_maxim.clear()
lant_maxim.extend(path)

path.pop()
vizitat[q] = False

def lungime_lant(q, graf, vizitat):
lant_maxim = []
dfs_lant_maxim(q, graf, vizitat, [], lant_maxim)
return len(lant_maxim), lant_maxim

def gaseste_lant_maxim(n, muchii, q):
graf = {i: [] for i in range(1, n + 1)}
for u, v in muchii:
graf[u].append(v)
graf[v].append(u)

vizitat = {i: False for i in range(1, n + 1)}

lungime_maxima = 0
lant_maxim = []

for v in range(1, n + 1):
if not vizitat[v]:
lungime, lant = lungime_lant(v, graf, vizitat)
if lungime > lungime_maxima:
lungime_maxima = lungime
lant_maxim = lant

return lant_maxim

def scrie_lant_maxim(file_path, lant_maxim):
with open(file_path, 'w') as file:
file.write(' '.join(map(str, lant_maxim)) + '\n')

if __name__ == "__main__":
file_in = "lantmaxim1IN.txt"
file_out = "lantmaxim1OUT.txt"

n, muchii, q = citeste_graf(file_in)
lant_maxim = gaseste_lant_maxim(n, muchii, q)

if lant_maxim:
scrie_lant_maxim(file_out, lant_maxim)
else:
with open(file_out, 'w') as file_out:
file_out.write("Nu corespunde restrictiilor impuse")

</syntaxhighlight>

4152 - Lant Maxim 1 - Revision history