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 ⩽ lungime sir s ⩽ 100
• 1 ⩽ m ⩽ 100
• Toate caracterele din sirul 's' sunt distincte.

Exemplu 1

Intrare

abc
2
a b
b c

Iesire

cba

Exemplu 2

Intrare

abcdef
3
a b
c d
e f

Iesire

Rearanjare imposibilă

Rezolvare

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()