#include <cstdlib>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void ecritureTailles(int n, int m, int comp[]);
void composantes(int n, int m, int edge[][2], int comp[]);
void grapheRandom(int,int, int[][2]);
void printgraphe (int, int, int[][2]);
void ecritureTaillesbis(int n, int m, int comp[]);

int main(int argc, char ** argv)
{
  int n;     // Nombre de sommets.
  int m;     // Nombre d'aretes.
  cout << "Entrer le nombre de sommets:";
  cin >> n;
  cout << "Entrer le nombre d'aretes:";
  cin >> m;
  int edge[m][2];    // Tableau des aretes.
  int comp[n];       // comp[i] est le numero de la composante contenant i.
  grapheRandom(n,m,edge);
  //printgraphe(n,m,edge);
  composantes(n,m,edge,comp);
  cout<<endl<<endl;
  ecritureTailles(n,m,comp);
  ecritureTaillesbis(n,m,comp);

  return EXIT_SUCCESS;
}
void ecritureTaillesbis(int n, int m, int comp[]){
  for (int i = 0 ; i < n; i ++){
    cout << "Le sommet : " << i << " est dans la composante : "<<comp[i]<<endl;
  }
}
void ecritureTailles(int n, int m, int comp[]){
  int comptemp[n];
  int compteur = 0;
  int tab[n];//n sera le nombre de cellule dans la composante, t[n] sera le nombre de composantes de tant de cellules
  for(int i =0 ; i <n; i ++){
    comptemp[i]=0;
    tab[i]=0;
  }
  for (int i = 0 ; i < n; i ++){
    if (comptemp[comp[i]]==0) compteur ++;
    comptemp[comp[i]] ++; //comptemp est a present un tableau qui pour n numero d'une composante associe le nombre de cellule incluses
  }
  for (int i =0; i < n; i ++){
    tab[comptemp[i]-1]++;
  }

  cout<<"Il y a "<<compteur<<" composantes connexes"<<endl;
  cout<<"Lesquelles sont : "<< endl;
  for (int i = 0 ; i<n; i ++){
    if (tab[i]>=1){
      cout<<"Il y a "<< tab[i] << " composantes de taille "<< i+1 << " Sommets, le num de cette comp est : "<< comp[i]<<endl;
    }
  }
}
void composantes(int n, int m, int edge[][2], int comp[]){
  int taille[n];
  vector<int> L[n];
  for (int i = 0 ; i < n; i ++) {
    comp[i]=i;
    taille[i]=1;
    L[i].push_back(i);
  }
  for ( int i = 0 ; i < m; i ++){
    int * x = &comp[edge[i][0]];
    int * y = &comp[edge[i][1]];
    if (*x != *y){
      if (*x>*y){
        int aux = *x;
        taille[*y]+=taille[aux];
        for(int j = 0; j < taille[aux]; j ++){
          int tmp = L[aux].back();
          comp[tmp]=*y;
          L[*y].push_back(tmp);
          L[aux].pop_back();
        }
      }
    }
  }
}

void printgraphe (int n, int m, int edge[][2]){
  cout<<n<<" Sommets et "<<m<<" aretes"<<endl;
  for (int i = 0 ; i < m; i ++){
    cout << "Arete "<< i << ":[" <<edge[i][0]<< ";"<<edge[i][1]<<"]";
  }
  cout<<endl;
}

void grapheRandom(int n,int m, int edge[][2]){
  srand(time(NULL));
  for (int i = 0; i < m;i ++){
    edge[i][0]=rand()%n;
    edge[i][1]=rand()%n;
  }
}