Cod sursa(job #1642882)

Utilizator tidehyonBosoi Bogdan tidehyon Data 9 martie 2016 16:41:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

int N, M, deg[50100], Q[50100];
vector <int> G[50100];

void solve()
{
    int i, x;
    vector <int>::iterator it;
    for(x = 1; x <= N; x++)
        if(deg[x] == 0)
            Q[++Q[0]] = x;
   for(i = 1; i <= N; i++)
   {
       x = Q[i];
       for(it = G[x].begin(); it != G[x].end(); ++it)
       {
           deg[*it]--;
           if(deg[*it] == 0) Q[++Q[0]] = *it;
       }
   }

}
void write()
{
    for(int i = 1; i <= N; i++)
        out << Q[i] << " ";
}

int main()
{
        in >> N >> M;
        int a,b;
        for(int i = 1; i <= M; i++)
        {
            in >> a >> b;
            G[a].push_back(b);
            deg[b]++;
        }
        in.close();
        solve();
        write();
        return 0;
}