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 toate lanțurile elementare cu extremitățile `p` și `q`. = Date de intrare = Fişierul de intrare `lantIN.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-30T12:45:22Z
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 toate lanțurile elementare cu extremitățile <code>p</code> și <code>q</code>.  = Date de intrare = Fişierul de intrare <code>lantIN.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ă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine toate lanțurile elementare cu extremitățile <code>p</code> și <code>q</code>.



= Date de intrare =

Fişierul de intrare <code>lantIN.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>lantOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <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.Î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>



= Exemplul 1: =

<code>lantIN.txt</code>

 5 8

 1 4 

 1 3 

 3 5 

 4 5 

 2 4 

 1 2 

 4 2 

 3 4

 2 5

<code>lantOUT.txt</code>

 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 



= Exemplul 2: =

<code>lantIN.txt</code>

 1000 100

 1 4 

 1 3 

 3 5 

 4 5 

 2 4 

 1 2 

 4 2 

 3 4

 2 5

<code>lantOUT.txt</code>

 Datele nu corespund restrictiilor impuse



== Rezolvare ==

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

def verifica_restrictii(n, muchii, p, 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 <= p <= n) or not (1 <= q <= n):

        return False

    return True



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:

            p, q = map(int, file.readline().split())

        except ValueError:

            with open("lantOUT.txt", 'w') as file_out:

                file_out.write("Datele nu corespund restrictiilor impuse")

            exit()



    if not verifica_restrictii(n, muchii, p, q):

        with open("lantOUT.txt", 'w') as file_out:

            file_out.write("Datele nu corespund restrictiilor impuse")

        exit()



    return n, muchii, p, q



def dfs(v, tinta, graf, vizitat, path, rezultat):

    vizitat[v] = True

    path.append(v)



    if v == tinta:

        rezultat.append(path.copy())

    else:

        for vecin in graf[v]:

            if not vizitat[vecin]:

                dfs(vecin, tinta, graf, vizitat, path, rezultat)



    path.pop()

    vizitat[v] = False



def gaseste_lanturi(n, muchii, p, 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)}

    rezultat = []



    dfs(p, q, graf, vizitat, [], rezultat)



    rezultat = list(set(tuple(lant) for lant in rezultat))

    rezultat.sort()



    return rezultat



def scrie_lanturi(file_path, lanturi):

    with open(file_path, 'w') as file:

        for lant in lanturi:

            file.write(' '.join(map(str, lant)) + '\n')



if __name__ == "__main__":

    file_in = "lantIN.txt"

    file_out = "lantOUT.txt"



    n, muchii, p, q = citeste_graf(file_in)

    rezultat = gaseste_lanturi(n, muchii, p, q)

    scrie_lanturi(file_out, rezultat)



</syntaxhighlight>
0475 - Lant - Revision history
