Cod sursa(job #951529)

Utilizator mihai10stoicaFMI - Stoica Mihai mihai10stoica Data 20 mai 2013 20:22:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 50005
int main()
{
    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");
    int n,m,i,a,b,x;
    int grad[MAXN];
    queue<int> q;
    vector<int> G[MAXN];
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>a>>b;
        G[a].push_back(b);
        grad[b]++;
    }
    in.close();
    for(i=1;i<=n;i++)
        if(grad[i]==0)
            q.push(i);
    vector<int>::iterator it;
    for(i=1;i<=n;i++)
    {
        x=q.front();q.pop();out<<x<<" ";
        for(it=G[x].begin();it!=G[x].end();++it)
        {
            grad[*it]--;
            if(grad[*it]==0) q.push(*it);
        }
    }
    out.close();
    return 0;
}