#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include<vector>
#include<queue>
#include<stack>

typedef struct coord{int abs; int ord;} coord;
bool search (std::vector<int> vec, int x);
void ecritureNiveaux(int n, int niveau[]);
void voisinsRandom(int n, int m, std::vector<int>voisins[]);
void afficheGraph (int n, std::vector<int>voisins[]);
void parcoursLargeur(int n, std::vector<int>voisins[],int niveau[], int ordre[], int pere[]);
void afficheArbre(int n, int pere[], int ordre[]);
void pacoursProf(int n, int r, std::vector<std::stack<int>*> voisins, int debut[],int fin[], int pere[], int niveau[]);
void vectortostack(int n,std::vector<int> arch[], std::vector<std::stack <int>* > young);
void afficheArbrebis(int n, int pere[]);
int sommeniveau(int n, int niveau[]);
using namespace std;

void voisinsRandom(int n, int m, vector<int>voisins[]){
  srand(time(NULL));
  int x=1; int y=0;
  for (int i = 0; i < m; i ++){
    do {
    x = rand()%n;
    y = rand()%n;
    while (x==y){
      y = rand()%n;
    }
  } while (search(voisins[x],y));
    voisins[x].push_back(y);
    voisins[y].push_back(x);
  }
}
bool search (vector<int> vec, int x){
  int i = 0;
  if (vec.size()==0){
    return false;
  }
  while (vec[i]!=x){
    i ++;
    if (i>vec.size()){
      return false;
    }
  }
  return true;
}
int main() {
  int n;            //Le nombre de points.
  int m; // nb aretes
  cout << "Entrer le nombre de points: ";
  cin >> n;
  cout << "Entrer le nombre d'aretes: ";
  cin>>m;
  if (m > n*(n-1)/2){
    cout<<"Nombre d'aretes trop grand, cap à : "<< n*(n-1)/2<<endl;
    m=n*(n-1)/2;
  }
  vector<int> voisins[n];
  int pere[n];
  int pere2[n];
  int ordre[n];
  int niveau[n];
  int niveau2[n];
  int debut[n];
  int fin[n];
  vector<stack < int >* > piledevoisins = vector< stack < int > * >(n);
  for (int i =0; i < n; i ++){
    piledevoisins[i]=new stack<int>;
  }
  // for (int i = 0; i < n ; i ++){
  //   piledevoisins[i]=new stack<int>;
  // }
  voisinsRandom(n,m,voisins);
  //afficheGraph(n,voisins);
  parcoursLargeur(n,voisins,niveau,ordre,pere);
  //afficheArbre(n, pere, ordre);
  //ecritureNiveaux(n,niveau);
  cout<<"Parcours en largeur OK"<<endl;
  vectortostack(n, voisins, piledevoisins);
  pacoursProf(n,0,piledevoisins, debut, fin, pere2, niveau2);
  //afficheArbrebis(n,pere);
  //ecritureNiveaux(n,niveau2);
  cout<<"Parcours Prof OK"<<endl;
  cout<<"Smax larg vaut : "<< sommeniveau(n,niveau)<<endl;
  cout<<"Smax prof vaut : "<< sommeniveau(n,niveau2)<<endl;
  return EXIT_SUCCESS;
}

int sommeniveau(int n, int niveau[]){
  int ret = 0;
  for (int i =0; i < n; i ++){
      ret+=niveau[i];
      // cout << niveau[i]<<" + ";
  }
  cout<<endl;
  return ret;
}
void afficheGraph (int n, vector<int>voisins[]){
  for (int i =0; i < n; i ++){
    int j = 0;
    cout<<"Sommet "<<i<< " Voisins : ";
    while (voisins[i].size()>j){
      cout<< " "<<voisins[i][j];
      j ++;
    }
    cout<<endl;
  }
}
void afficheArbre(int n, int pere[], int ordre[]){
  for (int i =0; i < n; i  ++ ){
    cout << "Pere de "<<i<<" : "<<pere[i]<<endl;
    cout << "Ordre de "<<i<<" : "<<ordre[i]<<endl;

  }
}
void afficheArbrebis(int n, int pere[]){
  for (int i =0; i < n; i  ++ ){
    cout << "Pere de "<<i<<" : "<<pere[i]<<endl;
  }
}
void parcoursLargeur(int n, vector<int>voisins[],int niveau[], int ordre[], int pere[]){
  int dejavu[n];
  for (int i =0; i < n; i ++ ){
    dejavu[i]=0;
    niveau[i]=0;
  }
  int r=0;
  dejavu[r]=1;
  ordre[r]=1;
  pere[r]=r;
  niveau[r]=0;
  queue<int> AT;
  AT.push(r);
  int t = 2;
  while (!AT.empty()){
    int v = AT.front();
    AT.pop();
    for (int i =0; i < voisins[v].size();i ++){
      int x = voisins[v][i];
      if (!dejavu[x]){
        dejavu[x]=1;
        AT.push(x);
        ordre[x]=t;
        t ++;
        pere[x]=v;
        niveau[x]=niveau[v]+1;
      }
    }
  }
}
void pacoursProf(int n, int r, vector<stack<int>* > voisins, int debut[],int fin[], int pere[] ,int niveau[]){
  bool dejavu[n];
  for (int i =0; i < n; i ++ ){
    dejavu[i]=false;
    niveau[i]=0;
  }
  dejavu[r]=1;
  debut[r]=1;
  pere[r]=r;
  niveau[r]=0;
  stack<int> AT;
  AT.push(r);
  int t = 2;
  while (!AT.empty()){
    int x = AT.top();
    if (voisins[x]->empty()){
      AT.pop();
      fin[x]=t;
      t ++;
    }
    else {
      int y = voisins[x]->top();
      voisins[x]->pop();
      if (!dejavu[y]){
        dejavu[y]=true;
        AT.push(y);
        debut[y]=t;
        t++;
        pere[y]=x;
        niveau[y]=niveau[x]+1;
        cout << "Niveau de "<<y << " = "<<niveau[x]+1<<endl;
      }
    }
  }
}
void vectortostack(int n,vector<int> arch[], vector<stack <int>* > young){
  for (int i = 0; i < n; i ++ ){
    for (int j =0; j < arch[i].size(); j++){
      young[i]->push(arch[i][j]);
    }
  }
}
void ecritureNiveaux(int n, int niveau[]){
  int tmp[n];
  for (int i =0; i < n; i ++){
    tmp[i]=0;
  }
  for (int i = 0 ; i < n; i ++ ){
    tmp[niveau[i]]++;
  }
  for (int i = 0; i < n; i ++){
    if (tmp[i]==0){
      return;
    }
    // cout<< "Il y a "<< tmp[i]<< " sommets de niveau " <<i<<endl;
  }
}
void distances(int n, int m, coord point[], int edge[][3]){
  int k = 0;
    for (int i =0; i < n; i ++){
      for(int j = i+1; j < n; j ++){
        edge[k][0]=i;
        edge[k][1]=j;
        edge[k][2]=(pow(point[j].abs-point[i].abs,2)+pow(point[j].ord-point[i].ord,2));
        k++;
      }
    }
    cout<<"calcul des distance : OK"<<endl;
}