Enunt

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 k reprezentând numărul de flori dintr-un buchet, să se determine grupele care se formează.

Date de intrare

Fişierul de intrare flori2.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale n şi k, 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 k valori separate prin câte un spaţiu reprezentând tipurile de flori culese.

Date de ieșire

Fişierul de ieşire flori2.out 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<=k<=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ă.

Exemplu

flori2.in

5 4
1 2 3 4
5 6 9 6
1 1 1 1 
2 4 4 3
7 7 7 7

flori2.out

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.

#include<iostream>
#include<stdio.h>
FILE *f=fopen("flori2.in","r");
FILE *g=fopen("flori2.out","w");

int n,k,a[150][150];  

int irelj(int i,int j) //verifica daca fata i e in relatie cu j(au cel putin o floare in comun)
{int u,v;
 for(u=1;u<=a[i][0];u++)   //a[i][0] e numarul de elemente pe linia i
    for(v=1;v<=a[j][0];v++)
      if (a[i][u]==a[j][v])
         return 1;
 return 0;
}
int apartine(int val,int linie) //caut val in multimea de pe linia linie
{int j,lg=a[linie][0];
 for(j=1;j<=lg;j++)
    if (val==a[linie][j])
        return 1;
 return 0;
}

void reuneste(int i,int j) //reuneste in linia i linia j
{int u;
 for(u=1;u<=a[j][0];u++)
    if(!apartine(a[j][u],i))
      {a[i][0]++;
        a[i][ a[i][0] ]=a[j][u];
      }
}

int main()
{int viz[150],i,j,val,ok;
 fscanf(f,"%d %d",&n,&k);
 for(i=1;i<=n;i++)
  for(j=1;j<=k;j++)
    {fscanf(f,"%d",&val);
     if(!apartine(val,i))
        {a[i][0]++;  //pe prima coloana am nr. de tipuri distincte de flori
         a[i][ a[i][0] ]=val;  //in multimea de pe linia i am tipurile distincte de flori al fetitei i
        }
    }
 for(i=1;i<=n;i++)
  viz[i]=i;     //initial exista n grupe
 for(i=1;i<=n;i++)
  {ok=0;
    if(a[i][0])
    {
     for(j=i+1;j<=n;j++)
        if(irelj(i,j))
            {
                viz[j]=viz[i];  //j trebuie sa ajunga in grupa cu i
                reuneste(i,j);  //reunesc in linia i linia j
                a[j][0]=0;//consider ca in multimea j am 0 elemente acuma
                ok=1;
                }
            }
     if (ok) i--;//faptul ca am reunit in i cel putin o multime j implica sa continui cu aceeasi linie i
                     //daca as lasa i sa se incrementeze conform for-ului,ar gresi in sensul ca 
                     //pt. i rel j si i nu e in rel cu k si j rel k      
                     //ar pune j in grupa i dar k ar ajunge in alta grupa
  }


 for(i=1;i<=n;i++)
    if(viz[i])
     {fprintf(g,"%d ",i);
      for(j=i+1;j<=n;j++)
    if(viz[i]==viz[j])
        {fprintf(g,"%d ",j);
         viz[j]=0;       //ca sa nu mai fie prelucrat
        }
      fprintf(g,"\n");
     }
 fclose(g);
}