Cod sursa(job #1418638)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 13 aprilie 2015 16:09:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int N,M;
int grad[50005];
vector<int> v[50005];
queue<int> rez;

int main()
{
    f>>N>>M;
    FOR (i,1,M)
    {
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
        ++grad[y];
    }
    /*FOR (i,1,N)
    {
        for (int j=0;j<v[i].size();++j)
            cout<<v[i][j]<<' ';
        cout<<'\n';
    }*/
    FOR (i,1,N)
    {
        if (grad[i]==0)
            rez.push(i);
    }
    FOR (cont,1,N)
    {
        int i=rez.front();
        g<<i<<' ';
        rez.pop();
        for (unsigned int j=0;j<v[i].size();++j)
        {
            --grad[v[i][j]];
            if (grad[v[i][j]]==0)
                rez.push(v[i][j]);
        }
    }
    while (!rez.empty())
    {
        g<<rez.front()<<' ';
        rez.pop();
    }
    f.close();g.close();
    return 0;
}