Editing 4014 - Rearanjare Sir

== Cerința ==
Într-un depozit, mărfurile sunt aranjate pe rafturi sub formă de șiruri de caractere. Mărfurile trebuie rearanjate astfel încât fiecare caracter să fie adiacent în șirul rearanjat doar dacă exista o cale în graf între cele două caractere inițial. Să se determine o rearanjare validă a șirului de caractere pe baza conexiunilor date.
== Date de intrare ==
Programul citește de la tastatură:

Un șir de caractere s reprezentând mărfurile pe rafturi.
Un număr întreg m reprezentând numărul de conexiuni între caractere.
O listă de m perechi de caractere reprezentând conexiunile din graf.
== Date de ieșire ==
Pe ecran se va afișa un șir de caractere rearanjat conform conexiunilor din graf. Dacă nu există nicio rearanjare validă, se va afișa mesajul "Rearanjare imposibilă".
== Restricții și precizări ==
*1 &les; lungime sir '''s''' &les; 100
*1 &les; '''m''' &les; 100
* Toate caracterele din sirul 's' sunt distincte.
== Exemplu 1 ==
;Intrare
abc <br>
2<br>
a b<br>
b c

;Iesire
cba
== Exemplu 2 ==
;Intrare
abcdef<br>
3<br>
a b<br>
c d<br>
e f

;Iesire
Rearanjare imposibilă

== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict, deque

def citeste_date():
    try:
        s = input("Introduceți șirul de caractere: ")
        m = int(input("Introduceți numărul de conexiuni: "))
        conexiuni = []
        for _ in range(m):
            conexiune = input().strip().split()
            conexiuni.append(conexiune)
        return s, m, conexiuni
    except ValueError:
        return None, None, None

def construieste_graf(s, conexiuni):
    graf = defaultdict(list)
    for u, v in conexiuni:
        graf[u].append(v)
        graf[v].append(u)
    return graf

def bfs(graf, start, vizitat):
    coada = deque([start])
    componenta = []
    vizitat.add(start)
    
    while coada:
        nod = coada.popleft()
        componenta.append(nod)
        for vecin in graf[nod]:
            if vecin not in vizitat:
                vizitat.add(vecin)
                coada.append(vecin)
    
    return componenta

def rearanjeaza_caractere(s, conexiuni):
    graf = construieste_graf(s, conexiuni)
    vizitat = set()
    componente = []
    
    for caracter in s:
        if caracter not in vizitat:
            componenta = bfs(graf, caracter, vizitat)
            componente.append(componenta)
    
    rezultat = []
    for componenta in componente:
        if len(componenta) == 1:
            rezultat.append(componenta[0])
        else:
            sub_sir = ''.join(componenta)
            for caracter in s:
                if caracter in sub_sir:
                    sub_sir = sub_sir.replace(caracter, '')
                    sub_sir = caracter + sub_sir
            rezultat.append(sub_sir)
    
    rearanjat = ''.join(rezultat)
    
    if sorted(rearanjat) != sorted(s):
        return "Rearanjare imposibilă"
    return rearanjat

def main():
    s, m, conexiuni = citeste_date()
    
    if s is None or m is None or conexiuni is None:
        print("Datele de intrare nu corespund restricțiilor impuse.")
        return
    
    rezultat = rearanjeaza_caractere(s, conexiuni)
    print(rezultat)

if __name__ == "__main__":
    main()

</syntaxhighlight>