Cod sursa(job #1733948)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 26 iulie 2016 10:48:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 50005
#include <queue>

using namespace std;

int N,M;
vector<int> graf[NMAX];
int grad[NMAX];
void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graf[x].push_back(y);
        grad[y]++;
    }
}


void sortare()
{
    queue<int> q;
    for(int i=1;i<=N;i++)
        if(grad[i]==0)
            q.push(i);

    while(!q.empty())
    {
        int c = q.front();
        printf("%d ",c);
        for(vector<int>::iterator ii = graf[c].begin();ii!=graf[c].end();ii++)
        {
            grad[*ii]--;
            if(grad[*ii]==0)
                q.push(*ii);
        }
        q.pop();
    }

}


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


    return 0;
}