2 files changed, 101 insertions, 0 deletions
diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1
new file mode 100644
index 0000000..d5c434d
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1
diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc
new file mode 100644
index 0000000..c73ad89
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc
@@ -0,0 +1,101 @@
+#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;
+  }
+}