Cod sursa(job #1022096)

Utilizator a96tudorAvram Tudor a96tudor Data 4 noiembrie 2013 19:03:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
//sortare topologica

#include<cstdio>
#include<vector>
#include<queue>

#define pb push_back
#define N_MAX 50010

using namespace std;

vector <int> G[N_MAX];

queue<int> Q;

int deg[N_MAX],N;

bool pus[N_MAX];

inline void Solve()
{
    vector <int> :: iterator it;

    int x,i;

     for (i=1;i<=N;i++)
        if (deg[i]==0)
            {
                Q.push(i);
                pus[i]=true;
            }
            else pus[i]=false;

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

        printf("%d ",x);
        for (it=G[x].begin();it!=G[x].end();it++)
        {
            deg[*it]--;
            if (deg[*it]==0 && !pus[*it])
                {
                    Q.push(*it);
                    pus[*it]=true;
                }
        }
        Q.pop();
    }
    return;
}

inline void Read_Data()
{
    int M,i,x,y;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);
        deg[y]++;
        G[x].pb(y);
    }

    return;
}


using namespace std;
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    Read_Data();
    Solve();
    printf("\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}