Editing 1378 - Flori2

== Enunț ==
Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

== Cerința ==
Fiind dat un număr natural n reprezentând numărul fetiţelor şi numărul natural m reprezentând numărul de flori dintr-un buchet, să se determine grupele care se formează.

== Date de intrare ==
Fişierul de intrare flori2in.txt conţine pe prima linie, separate printr-un spaţiu, numerele naturale n şi m, reprezentând numărul de fetiţe şi respectiv numărul de flori din fiecare buchet. Fiecare dintre următoarele n linii conţine, pentru fiecare fetiţă, câte m valori separate prin câte un spaţiu reprezentând tipurile de flori culese.

== Date de ieșire ==
Fişierul de ieşire flori2out.txt va conţine pe fiecare linie câte o grupă formată din numerele de ordine ale fetiţelor separate prin câte un spaţiu, în ordine crescătoare, ca în exemplu.

== Restricții și precizări ==
* 1 &les; '''n''' &les; 150
* 1 &les; '''m''' &les; 100
* Tipul unei flori este un număr întreg din intervalul [0,100].
* Într-o grupă numerele de ordine ale fetiţelor trebuie date în ordine strict crescătoare.
* În fişierul de ieşire grupele vor fi afişate în ordinea crescătoare a numărului de ordine al primei fetiţe din grupă.

== Exemplul 1 ==
; Intrare
; flori2in.txt
: 5 4
: 1 2 3 4
: 5 6 9 6
: 1 1 1 1 
: 2 4 4 3
: 7 7 7 7
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; flori2out.txt
: 1 3 4 
: 2
: 5

=== Explicație ===
Fetiţele 1 şi 3 au cules amândouă flori de tipul 1, iar fetiţele 1 şi 4 au cules amândouă flori de tipurile 2, 3 şi 4, deci toate cele trei fetiţe (1, 3, 4) se vor afla în aceiaşi grupă. Fetiţele 2 şi 5 vor forma fiecare câte o grupă deoarece nu au cules flori de acelaşi tip cu nici una dintre celelalte fetiţe.

== Exemplul 2 ==
; Intrare
; flori2in.txt
: 151 4
: 1 2 3 4
: 5 6 9 6
: 1 1 1 1 
: 2 4 4 3
: 7 7 7 7
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python" line>
#1378 - Flori2

def valideaza_input(n, m, flori_fete):
    if not (1 <= n <= 150 and 1 <= m <= 100):
        return False

    for lista_flori in flori_fete:
        if len(lista_flori) != m:
            return False
        for tip_floare in lista_flori:
            if not (0 <= tip_floare <= 100):
                return False

    return True


def citeste_date_intrare():
    with open("flori2in.txt", "r") as file:
        n, m = map(int, file.readline().split())
        flori_fete = [list(map(int, file.readline().split())) for _ in range(n)]
    return n, m, flori_fete


def grupare_fete(n, flori_fete):
    grupuri = []
    vizitat = [False] * n

    def dfs(nod, grup):
        vizitat[nod] = True
        grup.append(nod + 1)

        for i in range(n):
            if not vizitat[i] and any(flor in flori_fete[nod] for flor in flori_fete[i]):
                dfs(i, grup)

    for i in range(n):
        if not vizitat[i]:
            grup = []
            dfs(i, grup)
            grupuri.append(sorted(grup))

    return grupuri


def scrie_date_iesire(grupuri):
    with open("flori2out.txt", "w") as file:
        for grup in grupuri:
            file.write(" ".join(map(str, grup)) + "\n")


if __name__ == "__main__":
    n, m, flori_fete = citeste_date_intrare()
    if valideaza_input(n, m, flori_fete):
        print("Datele de intrare corespund restricțiilor impuse")
        rezultat = grupare_fete(n, flori_fete)
        scrie_date_iesire(rezultat)
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")

</syntaxhighlight>