Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef vector<int> VE;
- typedef vector< vector<int> > DEST;
- int n, m;
- VE sol;
- DEST destins; //tasques per fer després de la tasca "i"
- VE graus; //nombre de tasques que cal fer abans que la tasca "i"
- void prioritats(int i){
- if(i == n){
- for(int j = 0; j < n-1; ++j) cout << sol[j] << " ";
- cout << sol[n-1] << endl;
- return;
- }
- for(int j = 0; j < n; ++j) if(graus[j] == 0){ //per totes les tasques no fetes i que podem fer
- sol[i] = j;
- graus[j] = -1; //feta
- for(int k = 0; k < destins[j].size(); ++k) --graus[destins[j][k]]; //decrementem el grau de qui tingui alguna dependencia
- prioritats(i+1);
- graus[j] = 0;
- for(int k = 0; k < destins[j].size(); ++k) ++graus[destins[j][k]];
- }
- }
- int main(){
- cin >> n;
- sol = VE(n);
- graus = VE(n);
- cin >> m;
- destins = DEST(n);
- int x,y;
- for(int i = 0; i < m; ++i){
- cin >> x >> y;
- destins[x].push_back(y);
- ++graus[y];
- }
- prioritats(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement