Cod sursa(job #963175)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 16 iunie 2013 18:46:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <deque>
#include <list>

using namespace std;

int n,m;

struct nod
{
   int grad_interior; 
   list<int> iese;
   
   //nod()
  // {
  //    grad_interior=0;   
  // }       
}v[50005];

int coada[50005];

int main()
{
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");
    int poz=0;
    int i,a,b;
    cin>>n>>m;
    for(i=0;i<m;i++)
    {
       cin>>a>>b;
       a--;
       b--;
       v[b].grad_interior++;
       v[a].iese.push_back(b);                
    }
    //cout<<"op1"<<endl;
    for(i=0;i<n;i++)
       if(v[i].grad_interior==0)
          coada[++poz]=i;               
    //cout<<"op2"<<endl;
    list<int>::iterator p;      
    for(i=1;i<=n;i++)
    {                                                      
       //cout<<"pas "<<i<<endl;
       //cout<<"PREGATIM"<<endl;
       cout<<coada[i]+1<<'\n';   
       //cout<<"REUSIT"<<endl;                                    
       //cout<<"se_intra"<<endl;
       for(p=v[coada[i]].iese.begin();p!=v[coada[i]].iese.end();p++)
       {                                        
          v[(*p)].grad_interior--;
          if(v[(*p)].grad_interior==0)
            coada[++poz]=*p;                                      
       }
       //cout<<"se iese"<<endl;
    }
    cin.close();
    cout.close();
   //system("PAUSE");
    return 0;
}