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 ⩽ n ⩽ 150
• 1 ⩽ m ⩽ 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

#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")