CosminVarlan

Untitled

Nov 27th, 2020
593
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// generator graf neorientat cu n componente conexe si cu costuri
  2. #include <iostream>
  3. #include <vector>
  4. #include <stdlib.h>     /* srand, rand */
  5. #include <time.h>       /* time */
  6. #include <fstream>
  7.  
  8. using namespace std;
  9.  
  10. int muchii[600002];
  11. int nr_muchii = 0;
  12.  
  13. ofstream fout("graf.txt");
  14.  
  15. struct nod {
  16.     int cc;             /// din ce componenta conexa face parte
  17.     vector<int> vecini; /// indicii nodurilor vecine
  18. };
  19.  
  20. nod noduri[200001];
  21. int fr[200001];
  22.  
  23. void adaugaVecin(int a, int b){
  24.     noduri[a].vecini.push_back(b);
  25. }
  26.  
  27. void refaDFS(int a, int newValForCC){
  28.     if (noduri[a].cc==newValForCC) return; /// deja l-am vizitat si probabil ca sunt intr-o bucla
  29.     noduri[a].cc = newValForCC;
  30.     for(int i=0; i<noduri[a].vecini.size(); i++)
  31.         refaDFS(noduri[a].vecini[i], newValForCC);
  32. }
  33.  
  34. int vecini(int x, int y){
  35.     for(int i=0; i<noduri[x].vecini.size(); i++)
  36.         if (y==noduri[x].vecini[i]) return 1;
  37.     return 0;
  38. }
  39.  
  40. int main()
  41. {
  42.     int n,m,cx;
  43.     int bn, bm, bcx, costmax;
  44.     cout << "Introduceti numarul de noduri: ";
  45.     cin >> n;
  46.     cout << "Introduceti numarul de muchii:";
  47.     cin >> m;
  48.     cout << "Introduceti numarul de componente conexe:";
  49.     cin >> cx;
  50.     cout << "Introduceti costul maxim (cel minim este 1):";
  51.     cin >> costmax;
  52.     bn=n,bm=m,bcx=cx;
  53.     srand (time(NULL));
  54.  
  55.  
  56.     int muchii_in_plus=0;
  57.  
  58.     for(int i=1; i<=n; i++)
  59.         noduri[i].cc=i;
  60.  
  61.     int conexe = n;
  62.     while (conexe>cx)
  63.     {
  64.         int x = rand() % n + 1;
  65.         int y = rand() % n + 1;
  66.         if (noduri[x].cc!=noduri[y].cc)
  67.         {
  68.             adaugaVecin(x,y);
  69.             adaugaVecin(y,x);
  70.             if (noduri[x].cc < noduri[y].cc) refaDFS(noduri[y].cc, noduri[x].cc);
  71.             if (noduri[x].cc > noduri[y].cc) refaDFS(noduri[x].cc, noduri[y].cc);
  72.             conexe--;
  73.             m--;
  74.  
  75.             muchii[nr_muchii] = x;
  76.             muchii[nr_muchii+1] = y;
  77.             nr_muchii+=2;
  78.         }
  79.     }
  80.     while(m)
  81.     {
  82.         int x = rand() % n + 1;
  83.         int y = rand() % n + 1;
  84.         if (x==y) continue;
  85.         if (noduri[x].cc==noduri[y].cc){
  86.             m--;
  87.             muchii[nr_muchii] = x;
  88.             muchii[nr_muchii+1] = y;
  89.             nr_muchii+=2;
  90.         }
  91.     }
  92.  
  93.     fout << n << ' ' << bm << '\n';
  94.     for(int i=0; i<nr_muchii; i+=2)
  95.     {
  96.         if (muchii[i]<muchii[i+1]) fout << muchii[i] << ' ' << muchii[i+1] << ' ' << (rand() % costmax + 1)<< '\n';
  97.         else fout << muchii[i+1] << ' ' << muchii[i]  << ' ' << (rand() % costmax + 1)<< '\n';
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
RAW Paste Data