Corjuc Eunice: Pagină nouă: = Cerinţa = Se dă un graf neorientat cu n vârfuri și un număr natural `q`. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful `q`. = Date de intrare = Fişierul de intrare `input.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 `...`


2024-01-04T00:26:41Z
Pagină nouă: = Cerinţa = Se dă un graf neorientat cu n vârfuri și un număr natural <code>q</code>. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>.  = Date de intrare = Fişierul de intrare <code>input.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>...
New page
= Cerinţa =

Se dă un graf neorientat cu n vârfuri și un număr natural <code>q</code>. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>.



= Date de intrare =

Fişierul de intrare <code>input.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>.



Pe ultima linie se află numărul <code>q</code>.



= Date de ieşire =

Fişierul de ieşire <code>output.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitatea finală în vârful <code>q</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. Dacă graful nu conține niciun lanț elementar format din cel puțin o muchie, cu extremitatea finală în vârful <code>q</code>, atunci se va afișa <code>NU EXISTA</code>.



= Restricţii şi precizări =



* <code>1 ≤ n ≤ 20</code>

* <code>1 ≤ q ≤ n</code>

* <code>1 ≤ i, j ≤ n</code>

* muchiile se pot repeta în fișierul de intrare



== Exemplul 1 ==

input.txt:



5 8



1 4 



1 3 



3 5 



4 5 



2 4 



1 2 



4 2 



3 4



5



output.txt:



1 2 4 3 5



1 2 4 5



1 3 4 5



1 3 5



1 4 3 5



1 4 5



2 1 3 4 5



2 1 3 5



2 1 4 3 5



2 1 4 5



2 4 1 3 5



2 4 3 5



2 4 5



3 1 2 4 5



3 1 4 5



3 4 5



3 5



4 1 3 5



4 2 1 3 5



4 3 5



4 5



== Exemplul 2 ==

input.txt:



99999 8



1 4 



1 3 



3 5 



4 5 



2 4 



1 2 



4 2 



3 4



5



Ouput:



Constraint violation: 1 ≤ n ≤ 20



== Rezolvare ==

<syntaxhighlight lang="python3" line="1">

def verify_constraints(n):

    if not (1 <= n <= 20):

        print("Constraint violation: 1 ≤ n ≤ 20 and 1 ≤ q ≤ n")

        exit()



def is_edge_chain(chain):

    for i in range(len(chain) - 1):

        if not graph[chain[i]][chain[i + 1]]:

            return False

    return True



def find_elementary_chains(v, end_vertex, path):

    path.append(v)

    if v == end_vertex and len(path) > 1:

        chains.append(path.copy())

    else:

        for neighbor in range(1, n + 1):

            if graph[v][neighbor] and neighbor not in path:

                find_elementary_chains(neighbor, end_vertex, path)

    path.pop()



def write_chains_to_file(chains, output_file):

    if not chains:

        output_file.write("NU EXISTA\n")

    else:

        chains.sort()

        for chain in chains:

            output_file.write(" ".join(map(str, chain)) + '\n')



if __name__ == "__main__":

    with open("input.txt", "r") as fin, open("output.txt", "w") as fout:

        n, m = map(int, fin.readline().split())

        

        verify_constraints(n)

        

        graph = [[False] * (n + 1) for _ in range(n + 1)]



        for _ in range(m):

            a, b = map(int, fin.readline().split())

            graph[a][b] = graph[b][a] = True



        end_vertex = int(fin.readline().strip())



        chains = []

        for start_vertex in range(1, n + 1):

            if start_vertex != end_vertex:

                find_elementary_chains(start_vertex, end_vertex, [])



        write_chains_to_file(chains, fout)



</syntaxhighlight>

4061 - Lant Q - Revision history