Cod sursa(job #881621)

Utilizator stefan.cStefan Cucea stefan.c Data 18 februarie 2013 13:04:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>v[50001];
int grad[50001],qe[50001];
int n,m;
void solve()
{   int i,nod;
    vector<int>::iterator it;
    for(i=1;i<=n;i++)
        if(grad(i)==0)
            qe[++qe[0]]=i;
    for(i=1;i<=n;i++)
    { nod=qe[i];
      for(it=v[nod].begin();it!=v[nod].end();++it)
      {
          grad[*it]--;
          if(grad[*it]==0)
            qe[++qe[0]]= *it;
      }

    }
}
int main()
{int i,a,b;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
    scanf("%d%d",&a,&b);
    v[a].push_back(b);
    grad[b]++;
}
solve();
for(i=1;i<=n;i++)
    printf("%d ",qe[i]);
return 0;
}