Simina at 14:53, 27 December 2023

2023-12-27T14:53:27Z

← Older revision		Revision as of 14:53, 27 December 2023
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-un spațiu.		Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-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 =		= Restricții și precizări =

Simina at 21:35, 26 December 2023

2023-12-26T21:35:38Z

← Older revision		Revision as of 21:35, 26 December 2023
Line 37:		Line 37:
	<code>arboreOUT.txt</code>		<code>arboreOUT.txt</code>
	Datele nu corespund restrictiilor impuse		Datele nu corespund restrictiilor impuse

			== Rezolvare ==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3">
	def verifica_restrictii(n, k, muchii):		def verifica_restrictii(n, k, muchii):

Simina: Pagină nouă: = Cerința = Se dau cele `n-1` muchii ale unui arbore cu `n` noduri și un nod `k` . Afișați vectorul de tați al arborelui cu rădăcina în `k`. = Date de intrare = Fișierul de intrare `arboreIN.txt` conține pe prima linie numerele `n k`, Următoarele `n-1` linii vor conține câte o pereche `i j`, reprezentând muchiile arborelui. = Date de ieșire = Fișierul de ieșire `arb...`


2023-12-26T21:24:40Z
Pagină nouă: = Cerința = Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>.  = Date de intrare = Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui.  = Date de ieșire = Fișierul de ieșire <code>arb...
New page
= Cerința =

Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>.



= Date de intrare =

Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui.



= Date de ieșire =

Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-un spațiu.



= Restricții și precizări =



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

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

* în vectorul de tați rădăcina este marcată cu <code>0</code>



= Exemplul 1 : =

<code>arboreIN.txt</code>

 7 4

 1 2

 1 4

 1 7

 3 7

 5 7

 6 7

<code>arboreOUT.txt</code>

 4 1 7 0 7 7 1 



= Exemplul 2 : =

<code>arboreIN.txt</code>

 1000 1001

 1 2

 1 4

 1 7

 3 7

 5 7

 6 7

<code>arboreOUT.txt</code>

 Datele nu corespund restrictiilor impuse

<syntaxhighlight lang="python3">

def verifica_restrictii(n, k, muchii):

    if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:

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

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

        return False

    # Verifică dacă nodurile din muchii sunt în intervalul corect

    for muchie in muchii:

        if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):

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

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

            return False

    return True



def dfs(nod, parinte, graf, rezultat):

    rezultat[nod] = parinte

    for vecin in graf[nod]:

        if vecin != parinte:

            dfs(vecin, nod, graf, rezultat)



def main():

    # Citirea datelor de intrare

    with open("arboreIN.txt", "r") as file_in:

        n, k = map(int, file_in.readline().split())

        muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]



    # Verificarea restricțiilor

    if not verifica_restrictii(n, k, muchii):

        return



    # Construirea grafului

    graf = {i: [] for i in range(1, n + 1)}

    for muchie in muchii:

        graf[muchie[0]].append(muchie[1])

        graf[muchie[1]].append(muchie[0])



    # Inițializarea vectorului de tați cu 0

    parinti = [0] * (n + 1)



    # Apelarea algoritmului DFS

    dfs(k, 0, graf, parinti)



    # Scrierea rezultatului în fișierul de ieșire

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

        file_out.write(" ".join(map(str, parinti[1:])))



if __name__ == "__main__":

    main()



</syntaxhighlight>

0636 – Arbore - Revision history

Simina at 14:53, 27 December 2023

Simina at 21:35, 26 December 2023