Cod sursa(job #208492)

Utilizator Mishu91Andrei Misarca Mishu91 Data 16 septembrie 2008 19:47:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#define MAX_N 50100
#define pb push_back

using namespace std;

int G[MAX_N], N, M;
vector <int> V[MAX_N],Q;

void solve()
{
    for(int i = 1; i <= N; ++i)
        if(G[i] == 0)
            Q.pb(i);
    for(int p = 0; p < N; ++p)
    {
            int i = Q[p];
            for(int j = 0; j < V[i].size(); ++j)
            {
                G[V[i][j]] --;
                if(!G[V[i][j]])
                    Q.pb(V[i][j]);
            }
    }
}

int main()
{
    int x,y;
    freopen("sortaret.in","rt",stdin);
    freopen("sortaret.out","wt",stdout);
    scanf("%d %d",&N,&M);
    for(int i = 0; i < M; ++i)
    {
        scanf("%d %d",&x,&y);
        V[x].pb(y);
        G[y]++;
    }
    solve();
    for(int i = 0; i<Q.size(); ++i)
        printf("%d ",Q[i]);
}