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 nu conțin vârful `r`. = Date de intrare = Fişierul de intrare `lanturi1IN.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 î...

2023-12-30T13:33:10Z

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 nu conțin vârful <code>r</code>. = Date de intrare = Fişierul de intrare <code>lanturi1IN.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 î...

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 nu conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturi1IN.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>lanturi1OUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care nu 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>lanturi1IN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturi1OUT.txt</code>
2 1 4 5
2 4 5

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_edge(u, v, path, r, visited):
return v != r and v not in path and not visited[v]

def generate_paths(graph, p, q, r, n):
def backtrack(current, path, visited):
visited[current] = True

if current == q:
result.append(path[:])
visited[current] = False
return

for neighbor in graph[current]:
if is_valid_edge(current, neighbor, path, r, visited):
path.append(neighbor)
backtrack(neighbor, path, visited)
path.pop()

visited[current] = False

result = []
visited = {i: False for i in range(1, n + 1)}
backtrack(p, [p], visited)
return result

def check_restrictions(n, m, edges, p, q, r):
if not (1 <= n <= 20 and 1 <= p <= n and 1 <= q <= n and 1 <= r <= n and p != q != r):
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return False

for edge in edges:
u, v = edge
if not (1 <= u <= n and 1 <= v <= n):
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return False

return True

def main():
with open('lanturi1IN.txt', 'r') as input_file:
n, m = map(int, input_file.readline().split())
edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

line = input_file.readline().split()
if len(line) < 3:
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return

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

if not check_restrictions(n, m, edges, p, q, r):
return

graph = {i: [] for i in range(1, n + 1)}
for edge in edges:
u, v = edge
graph[u].append(v)
graph[v].append(u)

paths = generate_paths(graph, p, q, r, n)
unique_paths = [list(item) for item in set(tuple(path) for path in paths)]
unique_paths.sort()

with open('lanturi1OUT.txt', 'w') as output_file:
for path in unique_paths:
output_file.write(" ".join(map(str, path)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0477 - Lanturi 1 - Revision history