Mai intai trebuie sa te autentifici.

Cod sursa(job #1217064)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 6 august 2014 15:57:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

const int max_n = 50004;

queue <int> q;
vector <int> a[max_n];
int i,n,m,x,y,sol[max_n],nr;
int grad_interior[max_n];

void sortare_topologica(vector <int> a[max_n], int n, int sol[max_n]){
     int i,nr=0;
     
     for(i=1;i<=n;i++)
       if(!grad_interior[i]) q.push(i); 
     
     while(q.size())
          {
           int nod=q.front(); 
           sol[++nr]=nod;
           
           while(a[nod].size())
                {
                 int vecin=a[nod].back();
                 grad_interior[vecin]--;
                 if(!grad_interior[vecin]) q.push(vecin); 
                 a[nod].pop_back();
                }
           
           q.pop();         
          }
}

int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
                      fi>>x>>y;
                      a[x].push_back(y);
                      grad_interior[y]++;
                     }

    sortare_topologica(a,n,sol);
    
    for(i=1;i<=n;i++) fo<<sol[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}