Cod sursa(job #885743)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 22 februarie 2013 12:09:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <queue>
#define NM 50010

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N, M;
int i, j, a, b;
vector<int> G[NM];
int ANS[NM];
vector<int>::iterator it;
queue<int> Q;
int GR[NM];
bool In[NM];

int main ()
{
    f >> N >> M;
    for (i=1; i<=M; i++)
    {
        f >> a >> b;
        GR[b]++;
        G[a].push_back(b);
    }

    for (i=1; i<=N; i++)
        if (GR[i]==0)
        {
            Q.push(i);
            In[i]=1;
        }

    while (!Q.empty())
    {
        a=Q.front();
        Q.pop();
        ANS[++ANS[0]]=a;

        for (it=G[a].begin(); it!=G[a].end(); ++it)
            if (!In[*it])
            {
                GR[*it]--;
                if (GR[*it]==0)
                {
                    Q.push(*it);
                    In[*it]=1;
                }
            }
    }

    for (i=1; i<=N; i++)
        g << ANS[i] << ' ';

    g << '\n';

    f.close();
    g.close();

    return 0;
}