Cod sursa(job #1045119)

Utilizator paul_danutDandelion paul_danut Data 30 noiembrie 2013 21:48:04
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <vector>
#include <fstream>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
#define Nmax  50001
#define pb(x) push_back(x);

vector<int>::iterator it;
vector<int> a[Nmax];
int i,j,x,y,n,m,in[Nmax]={0},ex[Nmax],viz[Nmax]={0};

int main()
{

    f>>n>>m;
    for(i=1;i<=m;i++)
       {f>>x>>y;
       a[x].pb(y);
       in[y]++;
       ex[x]++;}

    for(i=1;i<=n;i++)
       {if(in[i]==0 && viz[i]==0)
            {g<<i<<' ';
            viz[i]=1;}
       if(in[i]==0&&ex[i]!=0)
          for(it=a[i].begin();it!=a[i].end();++it)
              if( viz[*it]==0 )
                  {if(in[*it]==1)
                    {g<<*it<<' ';
                    viz[*it]=1;}
                  else
                     in[*it]--;}}
    for(i=1;i<=n;i++)
       if(viz[i]==0)
          g<<i<<' ';

    f.close();g.close();
    return 0;
}