SHARE
TWEET

GRAFURI lab4 arbore

Diamyx Apr 25th, 2019 (edited) 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <utility>
  5. #include <algorithm>
  6. #include <fstream>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     ifstream fin("Lab3.in");
  12.     int n,s=0;
  13.     fin>>n;
  14.  
  15.     vector<int> d(n);
  16.  
  17.     if(fin.is_open())
  18.         for(int i=0; i<n; i++)
  19.         {
  20.             fin>>d[i];
  21.             if(d[i]>0) s+=d[i];
  22.             else
  23.             {
  24.                 s=-1;
  25.                 break;
  26.             }
  27.         }
  28.     fin.close();
  29.  
  30.     if(s!=2*(n-1))
  31.     {
  32.         cout<<"nu se poate construi\n";
  33.         return 0;
  34.     }
  35.     else
  36.     {
  37.         vector<int> tata(n,-1);
  38.         sort(d.begin(),d.end());
  39.         reverse(d.begin(),d.end());
  40.         int big_grad=n-1;
  41.         while(d[big_grad]==1)
  42.             big_grad--;
  43.         while(n>=3)
  44.         {
  45.             tata[n-1]=big_grad;
  46.             n--;
  47.             d[big_grad]--;
  48.             if(d[big_grad]==1) big_grad--;
  49.         }
  50.         tata[1]=0;
  51.         n=d.size();
  52.         for(int i=0; i<n; i++) cout<<tata[i]<<' ';
  53.         cout<<endl;
  54.  
  55.         vector<list<int> > fii(n);
  56.         for(int i=1; i<n; i++)
  57.             if(tata[i]!=-1) fii[tata[i]].push_back(i);
  58.  
  59.         for(int i=0; i<n; i++) //afisare
  60.             {
  61.                 cout<<i+1<<": ";
  62.                 for(list<int>::iterator it=fii[i].begin(); it!=fii[i].end(); it++)
  63.                 {
  64.                     cout<<*it+1<<' ';
  65.                 }
  66.                 cout<<endl;
  67.             }
  68.     }
  69.  
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top