Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu `n` vârfuri și trei vârfuri `p q r`. Să se determine toate lanțurile elementare cu extremitățile în `p` și `q` care conțin vârful `r`. = Date de intrare = Fişierul de intrare `lanturiIN.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 co...

2023-12-30T13:23:44Z

Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care conțin vârful <code>r</code>. = Date de intrare = Fişierul de intrare <code>lanturiIN.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 co...

New page

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturiIN.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 trei numere <code>p q r</code>, cu semnificația precizată.

= Date de ieşire =
Fişierul de ieşire <code>lanturiOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care conțin vârful <code>r</code>, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.Î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 , r ≤ n</code>
* <code>p</code>, <code>q</code> și <code>r</code> sunt diferite

= Exemplul 1: =
<code>lanturiIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturiOUT.txt</code>
2 1 3 4 5
2 1 3 5
2 1 4 3 5
2 4 1 3 5
2 4 3 5

= Exemplul 2: =
<code>lanturiIN.txt</code>
100 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturiOUT.txt</code>
Nu corespunde restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_lanturi_elementare(graph, p, q, r):
def dfs(curent, cale):
nonlocal rezultat
vizitat[curent] = True
cale.append(curent)

if curent == q:
if r in cale:
rezultat.add(tuple(cale))
else:
for vecin in graph[curent]:
if not vizitat[vecin]:
dfs(vecin, cale)

vizitat[curent] = False
cale.pop()

rezultat = set()
vizitat = [False] * (n + 1)
dfs(p, [])

return rezultat

def verifica_restrictii(n, p, q, r):
if not (1 <= n <= 20) or not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
return False
return True

def citeste_intrare(nume_fisier):
with open(nume_fisier, 'r') as fisier:
try:
n, m = map(int, fisier.readline().split())
graf = {i: [] for i in range(1, n + 1)}

for _ in range(m):
linie = fisier.readline().split()
if len(linie) != 2:
raise ValueError("Nu corespunde restrictiilor impuse")
i, j = map(int, linie)
graf[i].append(j)
graf[j].append(i)

linie = fisier.readline().split()
if len(linie) != 3:
raise ValueError("Nu corespunde restrictiilor impuse")

p, q, r = map(int, linie)

if not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
raise ValueError("Nu corespunde restrictiilor impuse")

except ValueError as e:
with open('lanturiOUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(f"Nu corespunde restrictiilor impuse")
exit()

return n, graf, p, q, r

def scrie_iesire(nume_fisier, lanturi):
with open(nume_fisier, 'w') as fisier:
if lanturi == "Nu corespunde restricțiilor impuse":
fisier.write(lanturi)
else:
for lant in lanturi:
fisier.write(' '.join(map(str, lant)) + '\n')

if __name__ == '__main__':
fisier_intrare = 'lanturiIN.txt'
fisier_iesire = 'lanturiOUT.txt'

n, graf, p, q, r = citeste_intrare(fisier_intrare)

if not verifica_restrictii(n, p, q, r):
scrie_iesire(fisier_iesire, "Nu corespunde restrictiilor impuse")
else:
lanturi = gaseste_lanturi_elementare(graf, p, q, r)
lanturi = [list(lant) for lant in lanturi]
lanturi.sort()

scrie_iesire(fisier_iesire, lanturi)

</syntaxhighlight>

0476 - Lanturi - Revision history