#include <cstdlib>
#include <iostream>
#include <vector>
#include<fstream>

using namespace std;


//---------------------------------------------------------------------------------
// Graphe oriente aleatoire sans boucle ni arc multiple
//---------------------------------------------------------------------------------

void Voisins_random(int n, int m, vector<int> voisin[]){	     // Calcule un graphe oriente aleatoire.
   srand(time(NULL));                
  for (int i=0;i<m;i++)              
    {int simple=0;
    int a,b;
    while (!simple)
      {simple=1;
      a=rand()%n;
      b=rand()%n;
      if (a==b) simple=0;
      for (int j=0;j<voisin[a].size();j++)           
        if (voisin[a][j]==b) simple=0;
      }  
    voisin[a].push_back(b); 
    }
}



//---------------------------------------------------------------------------------
// Affichage des listes de voisins
//---------------------------------------------------------------------------------


void Affiche(int n, vector<int> voisin[]){
  for(int i=0;i<n;i++){
    cout << "Voisins de " << i << " : ";
    for(int j=0;j<voisin[i].size();j++){
      cout << voisin[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl;
}


//---------------------------------------------------------------------------------
// Parcours en profondeur
//---------------------------------------------------------------------------------


void Parcours_en_profondeur(int n, int root, vector<int> voisin[], int debut[],
			    int fin[], int pere[]){       //On specifie la racine
  
  vector<int> listeVois[n];                  //Copie des listes de voisins, qui seront modifiees
  for(int i=0;i<n;i++){
    for(int j=0;j<voisin[i].size();j++){
      listeVois[i].push_back(voisin[i][j]);
    }
  }

  vector<int> atraiter;                      //Pile
  int dejavu[n];  		             //Variable testant si un sommet a ete vu.
  for(int i=0; i<n; i++){
    dejavu[i]=0;
  }


  int nbrDejavu=1;                           //Nombre de sommets traites


  atraiter.push_back(root);
  dejavu[root]=1;
  debut[root]=0;
  int Kdebut=1;                              //Date de debut
  int Kfin=0;                                //Date de fin




  while(nbrDejavu < n){                      //Tant qu'on n'a pas vu tout le monde.


    if(atraiter.empty()){                    //Si la liste de sommets a traiter est vide
      int i=0;                               //On cherche un sommet non deja vu
      while(dejavu[i]==1){
	i++;
      }
      atraiter.push_back(i);
      dejavu[i]=1;
      nbrDejavu++;
      debut[i]=Kdebut;
      Kdebut++;
    }
    
    while (!atraiter.empty()){               //Tant que la pile est non vide
     
      int x=atraiter.back();                 
      if (listeVois[x].empty()){             //Il n'y a plus de voisins atteignables depuis x
	atraiter.pop_back();
	fin[x]=Kfin;
	Kfin++;
      }
      else 
	{int y=listeVois[x].back();    
	listeVois[x].pop_back();
	if (dejavu[y]==0)                    //x a un voisin non deja vu
	  {dejavu[y]=1;
	  nbrDejavu++;
	  debut[y]=Kdebut;
	  Kdebut++;
	  pere[y]=x;
	  atraiter.push_back(y);
	  }
	}
    }
  }
}
 



//---------------------------------------------------------------------------------
// Fonction de test d'affichage du parcours en profondeur
//---------------------------------------------------------------------------------


void Affichage_du_Parcours(int n, vector<int> voisin[], int debut[],
			    int fin[], int pere[]){ 

  Parcours_en_profondeur(n,0,voisin,debut, fin, pere);
  for(int i=0;i<n;i++){
    cout << "Sommet " << i << " de pere " << pere[i] << " debut " << debut[i] << " fin " << fin[i] << endl;
  }


}



//---------------------------------------------------------------------------------
// Calcul des listes de voisins entrants
//---------------------------------------------------------------------------------

void Voisins_Entrants(int n, vector<int> voisin[], vector<int> entrant[]){
  
  //
  // A COMPLETER
  //

  //entrant[i] doit contenir la liste des voisins entrants du sommet i

}




//---------------------------------------------------------------------------------
// Un petit tri (a bulles...), s'en inspirer pour la fonction suivante
//---------------------------------------------------------------------------------

void Tri(int k, int tableau[]){
  for(int i=0;i<k-1;i++){
    for(int j=0; j<k-1-i; j++){
      if(tableau[j]>tableau[j+1]){
	int buf=tableau[j];
	tableau[j]=tableau[j+1];
	tableau[j+1]=buf;
      }
    }
  }
}



//---------------------------------------------------------------------------------
// Calcul des listes de voisins entrants triees selon la date de fin
//---------------------------------------------------------------------------------





void Tri_entrant(int k, vector<int> &tableau,int fin[]){

  //
  // A COMPLETER
  //

  //tableau est la liste des sommets entrants d'un sommet, on doit la trier par date de fin croissante


}



//---------------------------------------------------------------------------------
// Calcul des composantes fortement connexe
//---------------------------------------------------------------------------------

void cfc(int n, vector<int> voisin[]){

 int debut[n];                            // Date de premiere visite d'un sommet.
  int fin[n];                              // Date de derniere visite d'un sommet.
  int pere[n];                             // Les predecesseurs dand l'arbre en largeur.

  for(int i=0;i<n;i++){
    pere[i]=-1;
  }

  vector<int> entrant[n];

  Voisins_Entrants(n,voisin,entrant);       //calcul des voisins entrants

  Parcours_en_profondeur(n,0,voisin, debut, fin, pere);

  //Decommenter les 2 lignes suivantes pour afficher le parcours

  //Affichage_du_Parcours(n,voisin,debut,fin,pere);
  //cout<<endl;

  for(int i=0; i<n; i++){                   //on trie chaque liste de voisin entrant
    Tri_entrant(entrant[i].size(),entrant[i],fin);
  }

  Affiche(n,entrant);

  int finMax;


  //
  // A COMPLETER:
  //
  // CALCULER LE SOMMET DE DATE DE FIN MAXIMALE
  //



  Parcours_en_profondeur(n,finMax,entrant, debut, fin, pere);

  //
  // A COMPLETER
  //
  // AFFICHER LES COMPOSANTES FORTEMENT CONNEXES
  //


}

//---------------------------------------------------------------------------------
// Le main
//---------------------------------------------------------------------------------


int main(){



  int n=5;                                 // Le nombre de sommets.
  int m=6;                                 // Le nombre d'aretes.   
  vector<int> voisin[n];                   // Les listes de voisins des sommets, une liste par sommet.    
 


  Voisins_random(n,m, voisin);
  Affiche(n, voisin);
  cfc(n,voisin);
}