Cod sursa(job #1100827)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 7 februarie 2014 15:47:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define dmax 50001
#define nmax 100001
#define pb push_back

int gr[dmax], n, m;
vector <int> v[dmax];
queue <int> q;

void read()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

int a, b;
    scanf("%i %i", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%i %i", &a, &b);
        v[a].pb(b);
        gr[b]++;
    }
}

void BFS()
{
    int x;
while(!q.empty())
{
    x=q.front();
    q.pop();
    printf("%i ", x);
    for(int i=0;i<v[x].size();i++)
    {
        gr[v[x][i]]--;
        if(gr[v[x][i]]==0)
            q.push(v[x][i]);
    }
}


}

void fill_queue()
{
    for(int i=1; i<=n; i++)
        if(gr[i]==0)
            q.push(i);
}

int main()
{
    read();
    fill_queue();
    BFS();
return 0;
}