Editing 0636 – Arbore

= 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>