Cod sursa(job #1526287)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 16 noiembrie 2015 08:37:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <deque>
#define Nmax 50005
#define pb push_back
using namespace std;
FILE *f = freopen("sortaret.in", "r", stdin);
FILE *g = freopen("sortaret.out", "w", stdout);
vector<int>G[Nmax]; /// graful
int Deg[Nmax]; /// gradul exterior al nodului x
int Q[Nmax]; ///coada in care retin pe rand nodurile cu grad 0
int N, M, X, Y;
void read_data()
{
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=M; i++)
    {
        scanf("%d%d", &X, &Y);
        G[X].pb(Y);
        Deg[Y] ++;
    }
}
void solve()
{
        for(int i = 1; i<=N; i++)
        if(Deg[i] == 0) Q[++Q[0]] = i;
       for(int i = 1; i <= N; i++)
       {
           int x = Q[i];
           for(vector<int>::iterator it = G[x].begin(); it!= G[x].end(); ++it)
           {
               Deg[*it] --;
               if(Deg[*it] == 0) Q[++Q[0]] = *it;
           }
       }
}
void write_sol()
{
    for(int i = 1; i<=N; i++)
        printf("%d ", Q[i]);
}
int main()
{
    read_data();
    solve();
    write_sol();
    return 0;
}