#include <cstdlib>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const int n = 1000000;
const int m = 1000000;

int edge[m][2];
int comp[n];

void grapheview(void)
{
  int i;
  
  cout << "Arretes:" << endl;
  for(i = 0; i < m; ++i)
    {
      cout << "\t" << edge[i][0] << " - " << edge[i][1] << endl;
    }
  
  cout << "Composantes:" << endl;
  for(i = 0; i < n; ++i)
    {
      cout << "\t" << i << " : " << comp[i] << endl;
    }
}

void grapherandom(void)
{
  int i, j;
  
  srand(time(NULL));
  
  for(i = 0; i < m; ++i)
    {
      edge[i][0] = (int)floor(((double)rand() / RAND_MAX * n));
      edge[i][1] = (int)floor(((double)rand() / RAND_MAX * n));
    }
}

void composantes(void)
{
  int i;
  vector<int> vect[n];
  
  for(i = 0; i < n; ++i)
    {
      comp[i] = i;
      vect[i].push_back(i);
    }
  
  for(i = 0; i < m; ++i)
    {
      if(comp[edge[i][0]] != comp[edge[i][1]])
	{
	  int j, k, l;
	  if(vect[comp[edge[i][0]]].size() < vect[comp[edge[i][1]]].size())
	    {
	      k = comp[edge[i][0]];
	      l = comp[edge[i][1]];
	    }
	  else
	    {
	      k = comp[edge[i][1]];
	      l = comp[edge[i][0]];
	    }
	  while(!vect[k].empty())
	    {
	      comp[vect[k].back()] = l;
	      vect[l].push_back(vect[k].back());
	      vect[k].pop_back();
	    }
	}
    }
}

void ecrituretailles(void)
{
  int taillecomp[n];
  int nbComp[n + 1];
  int i;
  
  for(i = 0; i < n; ++i)
    {
      taillecomp[i] = 0;
      nbComp[i] = 0;
    }
  nbComp[n] = 0;
  
  for(i = 0; i < n; ++i)
    {
      taillecomp[comp[i]]++;
    }
  
  for(i = 0; i < n; ++i)
    {
      nbComp[taillecomp[i]]++;
    }
  
  cout << "Taille des composantes:" << endl;
  cout << "\tIl y a " << nbComp[1] << " points isoles." << endl;
  for(i = 2; i < n + 1; ++i)
    { 
      if(nbComp[i] != 0)
	{
	  cout << "\tIl y a " << nbComp[i] << " composantes de taille " << i << "." <<  endl;
	}
    }
}


int main(int argc, char* argv[])
{
  grapherandom();
  composantes();
  //grapheview();
  ecrituretailles();
  
  return 0;
}