From 9fe033ea88c2f705ec18c232873d056e0c229d72 Mon Sep 17 00:00:00 2001
From: Gaspard Coulet <gaspard.coulet@mines-ales.org>
Date: Wed, 28 Apr 2021 23:05:53 +0200
Subject: Initial commit

---
 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1    | Bin 0 -> 27229 bytes
 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc | 101 +++++++++++++++++++++++++++
 2 files changed, 101 insertions(+)
 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1
 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc

(limited to 'sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1')

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
Binary files /dev/null and b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 differ
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;
+  }
+}
-- 
cgit v1.2.3