Advertisement
Guest User

Ordenacions topologiques

a guest
Dec 21st, 2014
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. typedef vector<int> VE;
  7. typedef vector< vector<int> > DEST;
  8.  
  9. int n, m;
  10. VE sol;
  11. DEST destins;   //tasques per fer després de la tasca "i"
  12. VE graus; //nombre de tasques que cal fer abans que la tasca "i"
  13.  
  14. void prioritats(int i){
  15.     if(i == n){
  16.         for(int j = 0; j < n-1; ++j) cout << sol[j] << " ";
  17.         cout << sol[n-1] << endl;
  18.         return;
  19.     }
  20.     for(int j = 0; j < n; ++j) if(graus[j] == 0){ //per totes les tasques no fetes i que podem fer
  21.         sol[i] = j;
  22.         graus[j] = -1; //feta
  23.         for(int k = 0; k < destins[j].size(); ++k) --graus[destins[j][k]]; //decrementem el grau de qui tingui alguna dependencia
  24.         prioritats(i+1);
  25.         graus[j] = 0;
  26.         for(int k = 0; k < destins[j].size(); ++k) ++graus[destins[j][k]];
  27.     }    
  28. }
  29.  
  30. int main(){
  31.     cin >> n;
  32.     sol = VE(n);
  33.     graus = VE(n);
  34.     cin >> m;
  35.     destins = DEST(n);
  36.     int x,y;
  37.     for(int i = 0; i < m; ++i){
  38.         cin >> x >> y;
  39.         destins[x].push_back(y);
  40.         ++graus[y];
  41.     }        
  42.     prioritats(0);    
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement