Cod sursa(job #1610173)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 23 februarie 2016 12:23:34
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NMAX=50000;

vector <int> G[NMAX];
queue <int> q;

int v[NMAX],grad[NMAX];

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

    int n,m,i,a,b,cnt=0,x,y;

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

    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);

        G[a].push_back(b);
        grad[b]++;
    }

    for(i=1;i<=n;i++)
        if(grad[i]==0)
        {
            q.push(i);
            cnt++;
            v[cnt]=i;
        }

    while(!q.empty())
    {
        x=q.front();

        for(i=0;i<(int)G[x].size();i++)
        {
            y=G[x][i];
            grad[y]--;

            if(grad[y]==0)
            {
                q.push(y);
                cnt++;
                v[cnt]=y;
            }
        }

        q.pop();
    }

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

    return 0;
}