Cod sursa(job #892507)

Utilizator andreitulusAndrei andreitulus Data 26 februarie 2013 10:13:28
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<vector>
#define maxn 50002
using namespace std;

int n,m,d[maxn],q[maxn];
vector <int> v[maxn];


void cit()
{
    int i,a,b;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)
      scanf("%d %d",&a,&b),v[a].push_back(b),d[b]++;
}




void afis()
{
    int i;

    for(i=1;i<=n;i++)
     printf("%d ",q[i]);
}




void rez()
{
    int i,j,nr;

    for(i=1;i<=n;i++)
      if(d[i]==0)
        q[++q[0]]=i;


    for(i=1;i<=n;i++)
      {
          nr=v[i].size();

          for(j=0;j<nr;j++)
           {
               d[v[i][j]]--;

               if(d[v[i][j]]==0)
                 q[++q[0]]=v[i][j];
           }
      }
}



int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    cit();
    rez();
    afis();

    fclose(stdin);
    fclose(stdout);

    return 0;
}