Cod sursa(job #2139488)

Utilizator AndreosAndrei Otetea Andreos Data 22 februarie 2018 16:26:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX=50000;
int pred[NMAX+5],sol[NMAX+5];
vector <int> succ[NMAX+5];
queue <int> q;
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m,i,j,u,v,k=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
      scanf("%d%d",&u,&v);
      pred[v]++;
      succ[u].push_back(v);
    }
    for(i=1;i<=n;++i)
    {
      if(pred[i]==0)
        q.push(i);
    }
    while(!q.empty())
    {
      u=q.front();
      q.pop();
      for(j=0;j<succ[u].size();++j)
      {
        v=succ[u][j];
        pred[v]--;
        if(pred[v]==0)
          q.push(v);
      }
      sol[++k]=u;
    }
    for(i=1;i<=n;++i)
      printf("%d ",sol[i]);
    printf("\n");
    return 0;
}